第一个要求a和p互质,第二个和第三个是广义欧拉降幂,不要求a和p互质,但要求b和的大小关系。
例题:
洛谷P4139
处理出对应的
由于2的无穷多次幂,即可通过递归来解决
#include <bits/stdc++.h> using namespace std; #define int long long const int INF = 1e9; //求欧拉函数 inline int phi(int n){ int res,a; res = a = n; for(int i=2;i*i<=a;i++){ if(a % i) continue; res = res / i * (i - 1); while(!(a%i)) a /= i; } if(a > 1) res = res / a * (a - 1); return res; } //快速幂 inline int power(int a,int t,int p){ int res = 1; while(t){ if(t & 1) res = res * a % p; a = a * a % p; t >>= 1; } return res; } int tower(int c,int p){ if(p == 1) return 0; int t = phi(p); return power(c,tower(c,t)+t,p); } void solve(){ int p; cin >> p; cout << tower(2,p) << endl; } signed main(){ int t; cin >> t; while(t--){ solve(); } return 0; }