首页 > 代码库 > UVA 10692 Huge Mods(指数循环节)
UVA 10692 Huge Mods(指数循环节)
指数循环节,由于a ^x = a ^(x % m + phi(m)) (mod m)仅在x >= phi(m)时成立,故应注意要判断
//by:Gavin http://www.cnblogs.com/IMGavin/ //指数循环节 递归处理 #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<string> #include<algorithm> #include<map> #include<queue> #include<vector> #include<cmath> #include<utility> 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; }
UVA 10692 Huge Mods(指数循环节)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。