欧拉定理:
$a^{\varphi(m)}=1\ mod\ m$ 当 $a,m$ 互质的时,
可以用来化简幂次, 比如求 $7^{222}\ mod\ 10$ 因为 7 和 10 互质, 求出 $\varphi(10)=4$ 则 $7^4\ mod\ 10 =1$ , 提公因式 $7^{4*55+2}=1^{55}*7^2 =9=mod 10$
扩展欧拉定理:
推广到不互质的情况:
$a^{c}=a^{c\ mod\ \varphi(m)}$ 当 $gcd(a,m)=1$ 时
$a^{c}=a^{c}$ 当 $gcd(a,m)\neq1,c<\varphi(m)$ 时
$a^{c}=a^{c\ mod\ \varphi(m) + \varphi(m)}$ 当 $gcd(a,m)\neq1,c\geq\phi(m)$ 时
求欧拉函数:
- const int maxn = 100001;
- ll phi[maxn];
- void phi_table(ll n) {// 计算 1 到 n 的欧拉函数值
- for(ll i = 2; i <= n; i++)
- phi[i] = 0;
- phi[1] = 1;
- for(ll i = 2; i <= n; i++) {
- if(!phi[i]) {
- for(ll j = i; j <= n; j+=i) {
- if(!phi[j]) phi[j] = j;
- phi[j] = phi[j] / i * (i - 1);
- }
- }
- }
- }
- ll euler_phi(ll n) {
- ll k = (ll)sqrt(n + 0.5);
- ll ans = n;
- for(int i = 2; i <= k; i++) {
- if(n % i == 0) {
- ans = ans / i * (i - 1);
- while(n % i == 0) n /= i;
- }
- }
- if(n> 1) ans = ans / n * (n - 1);
- return ans;
- }
来源: http://www.bubuko.com/infodetail-2991989.html