首页 > 代码库 > Uva 10629 Huge Mods (指数循环节)
Uva 10629 Huge Mods (指数循环节)
题意:求 a1?a2?a3?. . .?aN mod m
思路:利用 和递归求解
代码:
#include <iostream> #include <string.h> #include <stdio.h> using namespace std; const int N=15; typedef long long ll; int MOD; int A[N],k; int phi(int n) { int rea = n; for(int i=2; i*i<=n; i++) { if(n % i == 0) { rea = rea - rea / i; while(n % i == 0) n /= i; } } if(n > 1) rea = rea - rea / n; return rea; } ll qmulti(ll a,ll b,ll m) { ll ans = 0; a %= m; while(b) { if(b & 1) { ans = (ans + a) % m; b--; } b >>= 1; a = (a + a) % m; } return ans; } ll qmod(ll a,ll b,ll m) { ll ans = 1; a %= m; while(b) { if(b & 1) { ans = qmulti(ans,a,m); b--; } b >>= 1; a = qmulti(a,a,m); } return ans; } ll Solve(int num,ll mod) { if(num==k) return A[num]%mod; ll tmp=phi(mod); ll c=Solve(num+1,tmp)+tmp; return qmod(A[num],c,mod); } int main() { char str[15]; int cnt=0; ll ans; while(scanf("%s",str)!=-1) { if(strcmp(str,"#")==0) break; sscanf(str,"%d",&MOD); scanf("%d",&k); for(int i=1;i<=k;i++) { scanf("%d",&A[i]); } ans = Solve(1,MOD); cnt++; cout<<"Case #"<<cnt<<": "<<ans<<endl; } return 0; }
Uva 10629 Huge Mods (指数循环节)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。