歐拉降冪：

從公式來看，需要使用快速冪運算和歐拉函數

#include<bits/stdc++.h>using namespace std; typedef __int64 LL;const int maxn = 1e6+100;char b[maxn];//歐拉函數 LL ouler(LL n){LL ans = n, a = n;for(LL i = 2; i * i <= a; i++){if(a % i == 0){ans -= ans / i;while(a % i == 0){a /= i;}}}if(a > 1){ans -= ans / a;}return ans; }//快速冪 LL quick_mod(LL a, LL b, LL mod){LL res = 1;while(b){if(b & 1) res = res * a % mod;a = a * a % mod;b >>= 1;}return res; }LL solve(LL a, char b[], LL mod){int len = strlen(b);LL phi = ouler(mod);LL tmp = 0;for(int i = 0; i < len; i++){tmp = tmp * 10 + (b[i] - '0');if(tmp > mod) break;}if(tmp <= mod) return quick_mod(a, tmp, mod);else{tmp = 0;for(int i = 0; i < len; i++)tmp = ( tmp * 10 + (b[i] - '0') ) % phi;return quick_mod(a, tmp + phi, mod);} }// A ^ B % p int main() {LL a, c;LL n = 0, tmp;while(scanf("%lld", &a) != EOF){scanf("%s%lld", b, &c);printf("%lld\n", solve(a, b, c));}return 0; }

?

擴展歐拉降冪

求 ? b個a的次冪

解法：

對于，我們可以直接使用歐拉降冪去求，但這個式子是a次冪，又該怎么辦？

那么他的下一步一定還是遞歸的形式已知往下，直到q == 1 時，向上返回結果，所以只需在歐拉降冪的基礎上加一個dfs

#include<bits/stdc++.h>using namespace std; typedef long long LL;const int maxn = 1e6+100;char b[maxn];//歐拉函數 LL ouler(LL n){LL ans = n, a = n;for(LL i = 2; i * i <= a; i++){if(a % i == 0){ans -= ans / i;while(a % i == 0){a /= i;}}}if(a > 1){ans -= ans / a;}return ans; }//快速冪 LL quick_mod(LL a, LL b, LL mod){LL res = 1;while(b){if(b & 1) res = res * a % mod;a = a * a % mod;b >>= 1;}return res; }LL solve2(LL a, LL b, LL mod){LL phi = ouler(mod);if(b <= mod) return quick_mod(a, b, mod);else{a = a % phi;return quick_mod(a, b+phi, mod);} }LL solve(LL a, char b[], LL mod){int len = strlen(b);LL phi = ouler(mod);LL tmp = 0;for(int i = 0; i < len; i++){tmp = tmp * 10 + (b[i] - '0');if(tmp > mod) break;}if(tmp <= mod) return quick_mod(a, tmp, mod);else{tmp = 0;for(int i = 0; i < len; i++)tmp = ( tmp * 10 + (b[i] - '0') ) % phi;return quick_mod(a, tmp + phi, mod);} }LL ans = 0;//遞歸的求2^(2^(2^(2.....))) /* int dfs(int p){if(p == 1) return 1;LL phi = ouler(p);return quick_mod(2, dfs(phi) + phi, p); }*///求a^(a^(a^(a^(a^...)))) b個a次冪 LL dfs(LL a, LL b, LL p){if(p == 1) return 0;if(b == 0) return 1;LL phi = ouler(p);LL tmp = dfs(a, b-1, phi);if(tmp <= phi && tmp) return quick_mod(a, tmp, p);else return quick_mod(a, tmp+phi, p); }// A ^ B % p int main() {int T;scanf("%d", &T);while(T--){LL a, b, m;scanf("%lld%lld%lld", &a, &b, &m);printf("%lld\n", dfs(a, b, m) % m);}return 0; }

?

總結

以上是生活随笔為你收集整理的欧拉降幂及其扩展欧拉降幂的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。