当前位置: 首页 > news >正文

洛谷题单指南-进阶数论-P5091 【模板】扩展欧拉定理

原题链接:https://www.luogu.com.cn/problem/P5091

题意解读:求ab % m,b超级大。

解题思路:

大数幂取模问题,通常要用到扩展欧拉定理,下面从欧拉函数开始介绍。

1、欧拉函数

定义:小于等于n的正整数中与n互质的数的个数,叫做n的欧拉函数值,记作φ(n),编程时记为phi(n)

n用整数分解定理可表示为p1a1p2a2...pnan,那么φ(n) = n * (1-1/p1) * (1-1/p2)...*(1-1/pn)

通过容斥原理+归纳法不难证明。

主要性质:

如果n是素数,φ(n) = n - 1

如果a,b互质,φ(a * b) = φ(a) * φ(b)

如果a是素数,b % a == 0,φ(a * b) = a * φ(b)

另外,如果要线性计算1~n所有数的φ(n),可以在欧拉筛的过程中进行递推计算:

for(int i = 2; i <= n; i++)
{if(!vis[i]) //i是素数{p[++cnt] = i; //加入素数表vis[i] = true; //标记i为合数phi[i] = i - 1; //计算phi[i]}for(int j = 1; j <= cnt; j++){if(i * p[j] > n) break;vis[i * p[j]] = true; //用最小素因子p[j]标记合数i * p[j]if(i % p[j] != 0){phi[i * p[j]] = phi[i] * (p[j] - 1);}if(i % p[j] == 0){phi[i * p[j]] = phi[i] * p[j];break;}}
}

2、欧拉定理

 如果a与n互质,则有aΦ(n) ≡ 1 ( mod n ),其中Φ(n)是关于n的欧拉函数

主要用来简化幂取模问题,如a,n互质,ab % n = ab%Φ(n) % n

3、费马小定理

欧拉定理的特殊情况,n是质数时aΦ(n) = an-1 ≡ 1 ( mod n )

主要用来求逆元,如求a模n的逆元,n是质数,由于an-1 ≡ 1 ( mod n ),a * an-2 ≡ 1 ( mod n ),因此a-1(mod n) = an-2

4、扩展欧拉定理

对于ab % n,a、n不一定互质

当b < Φ(n)时,直接用快速幂计算即可

当b >= Φ(n)时,ab % n = ab%Φ(n)+Φ(n) % n

5、问题分析

先计算Φ(m)

再判断b,如果b < Φ(m),先将b缩小b = b % Φ(m),再用快速幂计算ksm(a, b, m)

如果b >= Φ(m),b = b % Φ(m) + Φ(m),再计算ksm(a, b, m)

100分代码:

#include <bits/stdc++.h>
using namespace std;int a, m;
string b;int phi(int x)
{int res = x;for(int i = 2; i <= x / i; i++){if(x % i == 0){res = 1ll * res * (i - 1) / i;while(x % i == 0) x /= i;}}if(x != 1) res = 1ll * res * (x - 1) / x;return res;
}int equals(string a, string b)
{if(a.size() != b.size()) return a.size() - b.size();for(int i = 0; i < a.size(); i++){if(a[i] != b[i]) return a[i] - b[i];}return 0;
}int ksm(int a, int b, int p)
{int res = 1;while(b){if(b & 1) res = 1ll * res * a % p;a = 1ll * a * a % p;b >>= 1;}return res;
}int main()
{cin >> a >> m >> b;int phim = phi(m);string phis = ""; //phim的字符串表示int t = phim;while(t){phis.push_back('0' + (t % 10));t /= 10;}reverse(phis.begin(), phis.end());int r = 0;for(int i = 0; i < b.size(); i++){r = (r * 10ll + b[i] - '0') % phim; //当b < phi(m)时,b%phi(m)=b} if(equals(b, phis) >= 0) r = r + phim; //如果b >= phi(m),b = b%phi(m)+phi(m)cout << ksm(a, r, m) << endl;return 0;
}

 

http://www.sczhlp.com/news/147400/

相关文章:

  • jenkins maven nacos springboot profile实现多环境配置
  • RAG is really dead? 大模型和知识之间的桥梁没了? - spader
  • 个人网站空间怎么做网站建设免费域名
  • 到底建手机网站还是电脑网站枪战网页游戏在线玩
  • 一家做公司评估的网站成都网站建设qghl
  • 阿里买域名 电脑做网站淘宝宝贝链接怎么做相关网站
  • Qwen-Image技术报告
  • 温州给企业做网站金华市住房和城乡建设局网站
  • 网站为什么要改版电商后台管理系统
  • 母婴用品网站建设餐厅设计公司餐厅设计
  • 制作网站设计的技术有wordpress lovevideo
  • 西樵网站设计制作wordpress单页下载
  • 做企业内部管理网站要多久定制网页设计报价
  • 网站程序源码最像app的wordpress主题
  • 网站建设部署视频教程网站建设有什么样好的建设意见
  • 网站制作优化排名专业网站建设经费申请
  • 重庆企业网站seo小程序制作开发平台
  • 旅游公司网站开发与实现上海做网站较好的公司
  • 青岛 网站备案论坛网站开发外文文献
  • 网站挂到国外服务器建站网站都用不了的
  • soho的网站怎么做试用网站空间
  • 苍梧县网站建设wordpress 轮播图
  • 做网站公司郑州汉狮找合伙人的网站做淘宝
  • IOS-和安卓-AR-游戏开发指南-全-
  • Winform/C# 输出到Release VS中Release模式下生成去掉生成pdb文件
  • 手机网站qq代码网站推广计划至少包括
  • 网站关键词百度自然排名优化网站服务费算什么费用
  • 东莞做网站做什么赚钱做相册的网站 网易
  • 网站 当前时间 代码朗坤智能企业管理系统
  • 外留网站建设公司的网站备案手续