欧拉降幂快速幂用

必须a和p互质才能欧拉。第一个要求a和p互质第二个和第三个是广义欧拉降幂不要求a和p互质但要求b和的大小关系。1.先上一个普通的取模的快速幂ll pow(ll a, ll b, ll mod) { ll r 1; a a % mod; while (b 0) { if (b 1 1)r (r*a) % mod; b 1; a (a*a) % mod; } return r; }2.再来一个欧拉函数的板子这里运用了一个公式是 axa(x%φ(m)φ(m))(mod m)ll phi(ll n) { ll i,rean; for(i2;i*in;i) { if(n%i0) { rearea-rea/i; while(n%i0) n/i; } } if(n1) rearea-rea/n; return rea; }欧拉函数快速幂#include bits/stdc.h using namespace std; typedef long long ll; ll ph(ll x) { ll resx,ax; for(ll i2;i*ix;i) { if(a%i0) { resres/i*(i-1); while(a%i0) a/i; } } if(a1) resres/a*(a-1); return res; } ll quick_pow(ll a,ll b,ll mod) { ll ans1; while(b) { if(b1) ans(ans*a)%mod; a(a*a)%mod; b1; } return ans; } ll f(ll p) { if(p1) return 0; ll kph(p); return quick_pow(2,f(k)k,p); } int main() { int T; scanf(%d,T); while(T--) { ll p;scanf(%lld,p); printf(%lld\n,f(p)); } return 0; }#include bits/stdc.h #define ll __int64 #define mod 10000000007 using namespace std; char a[1000006]; ll x,z; ll quickpow(ll x,ll y,ll z) { ll ans1; while(y) { if(y1) ansans*x%z; xx*x%z; y1; } return ans; } ll phi(ll n) { ll i,rean; for(i2;i*in;i) { if(n%i0) { rearea-rea/i; while(n%i0) n/i; } } if(n1) rearea-rea/n; return rea; } int main() { while(scanf(%lld %s %lld,x,a,z)!EOF) { ll lenstrlen(a); ll pphi(z); ll ans0; for(ll i0;ilen;i) ans(ans*10a[i]-0)%p; ansp; printf(%lld\n,quickpow(x,ans,z)); } return 0; }