UVa - 10692 - Huge Mods-（幂的模）

2019-04-14 21:51发布

站内文章 / 模拟电子
11963 0 1084

代码： #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; #define M 1005 char str[25]; int n,m,ans; int a[25]; int pow_mod(int n,int k,int m) //快速幂 { int res=1; while(k>0) { if(k&1) res=res*n%m; n=n*n%m; k>>=1; } return res; } int euler_phi(int n) { int m=(int)sqrt(n+0.5); int ans=n; for(int i=2;i<=m;i++) { if(n%i==0) { ans=ans/i*(i-1); while(n%i==0) n/=i; } } if(n>1) ans=ans/n*(n-1); return ans; } int solve(int i,int mod) { if(i==n-1) { return a[i]%mod; } int phi=euler_phi(mod); int k=solve(i+1,phi)+phi; return pow_mod(a[i],k,mod); } int main() { int i,cas=0; while(scanf("%s",str)==1&&strcmp(str,"#")!=0) { sscanf(str,"%d",&m); scanf("%d",&n); for(i=0;i

热门文章