本文共 1377 字，大约阅读时间需要 4 分钟。
指数循环节，由于a ^x = a ^(x % m + phi(m)) (mod m)仅在x >= phi(m)时成立，故应注意要判断
//by:Gavin http://www.cnblogs.com/IMGavin///指数循环节 递归处理#include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long LL;const int N = 10008, INF = 0x3F3F3F3F;LL a[N], mod, n;int phi[N];void allPhi(int n){ memset(phi,0,sizeof(phi)); phi[1]=1; for(int i=2;i<=n;i++){ if(!phi[i]){//则i为素数 phi[i]=i; for(int j=i;j<=n;j+=i){ if(!phi[j]){ phi[j]=j; } phi[j]=phi[j]/i*(i-1); } } }}LL PowMod(LL a,LL b,LL MOD){ LL ret=1; while(b){ if(b&1){ ret = ret * a % MOD; } a = a * a % MOD; b>>=1; } return ret;}bool check(LL a, LL n, LL m){ if(a == 1){ return false; } LL ans = 1; for(int i = 0; i < n; i++){ ans *= a; if(ans >= m){ return true; } } return false;}LL dfs(LL d, LL m, bool &sym){ if(d == n){ if(a[d] >= m){ sym = 1; }else{ sym = 0; } return a[d] % m; } bool flag; LL p = dfs(d + 1, phi[m], flag); if(flag){ p += phi[m]; } sym = check(a[d], p, m); return PowMod(a[d], p, m);}int main(){ allPhi(N - 2); int t = 0; while(cin >> mod){ cin >> n; for(int i = 1; i <= n; i++){ cin >> a[i]; } bool flag; printf("Case #%d: %lld\n", ++t, dfs(1, mod, flag) % mod); } return 0;}
转载于:https://www.cnblogs.com/IMGavin/p/6124018.html