整数的阶：设a和n是互素的正整数，使得a^x=1（mod n）成立的最小的正整数x称为a模n的阶
//求阶模板：A^x=1(mod M),调用GetJie(A,M)//输入：10^10>A,M>1//输出：无解返回-1，有解返回最小正整数x//复杂度：O(M^(0.5))long long gcd(long long a,long long b){ if(b==0) return a; return gcd(b,a%b);}//欧拉函数:复杂度O(n^(0.5)),返回[1,n-1]中所有和n互素的数的个数和long long phi(long long x){ long long sum=x; for(long long i=2;i*i<=x;i++) { if(x%i==0) { sum=sum-sum/i; while(x%i==0) x/=i; } } if(x!=1) sum=sum-sum/x; return sum;}long long Mod_Mul(long long a,long long b,long long mod){ long long sum=0; while(b) { if(b&1) sum=(sum+a)%mod; b>>=1; a = (a+a)%mod; } return sum;}//a^b%mod 快速幂long long Quk_Mul(long long a,long long b,long long mod){ long long qsum=1; while(b) { if(b&1) qsum=Mod_Mul(qsum,a,mod); b>>=1; a=Mod_Mul(a, a, mod); } return qsum;}long long GetJie(long long A,long long M){ long long d = gcd(A,M); if(d != 1) return -1; long long m=phi(M); //然后对m进行拆分 long long prm[40],prmcnt[40]; int pcnt=0; memset(prmcnt,0,sizeof(prmcnt)); long long tm = m; for(long long i=2;i*i<=tm;i++) { if(tm%i==0) { prm[pcnt]=i; while(tm%i==0) { prmcnt[pcnt]++; tm/=i; } pcnt++; } } if(tm!=1) { prm[pcnt]=tm; prmcnt[pcnt]=1; pcnt++; } for(int i=0;i
//再加一个打素数表的。理论上会快10倍。
//求阶模板：A^x=1(mod M),调用GetJie(A,M)//输入：10^10>A,M>1//输出：无解返回-1，有解返回最小正整数x//复杂度：M^(0.5)long long PRIME[100100];long long gcd(long long a,long long b){ if(b==0) return a; return gcd(b,a%b);}//欧拉函数:复杂度O(n^(0.5)),返回[1,n-1]中所有和n互素的数的个数和long long phi(long long x){ long long sum=x; long long p = PRIME[0]; for(int i=0;p*p<=x;i++) { if(0 == x%p) { sum=sum-sum/p; while(x%p==0) x/=p; } p=PRIME[i+1]; } if(x!=1) sum=sum-sum/x; return sum;}long long Mod_Mul(long long a,long long b,long long mod){ long long sum=0; while(b) { if(b&1) sum=(sum+a)%mod; b>>=1; a = (a+a)%mod; } return sum;}//a^b%mod 快速幂long long Quk_Mul(long long a,long long b,long long mod){ long long qsum=1; while(b) { if(b&1) qsum=Mod_Mul(qsum,a,mod);//mod不是很大的时候这一步可以去掉 b>>=1; a=Mod_Mul(a, a, mod);// } return qsum;}long long GetJie(long long A,long long M){ long long d = gcd(A,M); if(d != 1) return -1; long long m=phi(M); //然后对m进行拆分 long long prm[40],prmcnt[40]; int pcnt=0; memset(prmcnt,0,sizeof(prmcnt)); long long tm = m; long long p=PRIME[0]; for(long long i=0;p*p<=tm;i++) { if(tm%p==0) { prm[pcnt]=p; while(tm%p==0) { prmcnt[pcnt]++; tm/=p; } pcnt++; } p=PRIME[i+1]; } if(tm!=1) { prm[pcnt]=tm; prmcnt[pcnt]=1; pcnt++; } for(int i=0;i