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

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

题意解读：求a^b % m，b超级大。

解题思路：

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

1、欧拉函数

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

n用整数分解定理可表示为p1^a1p2^a2...pn^an，那么φ(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互质，a^b % n = a^b%Φ(n) % n

3、费马小定理

欧拉定理的特殊情况，n是质数时a^{Φ(n) =} a^n-1 ≡ 1 ( mod n )

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

4、扩展欧拉定理

对于a^b % n，a、n不一定互质

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

当b >= Φ(n)时，a^b % n = a^{b%Φ(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;
}