本文主要是介绍hdu 3609 Up-up，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://acm.hdu.edu.cn/showproblem.php?pid=3609
这题主要是用到一个公式： A^X % C= A^(X%phi(C)+phi(C)) % C (X>=phi(C)),详细证明我也不知道，囧……
这个题设计的一个细节就是 要 x >= phi(C) ,我们分两种情况讨论：
1） 当x<phi(C) 的时候x=x%phi(C) 所以取不取模都对A的指数都没影响。
2） 当x>=phi(C) 的时候x !=x%phi(C) ，所以加上phi(C) 作为上层A的指数；
可能还没说明白，当初我学的时候也是想了好久，网上的代码就是一个公式，感觉他们讲的不清楚，具体还是看代码注释吧！
#include <iostream>
#include <cstdio>using namespace std;
typedef unsigned long long ll;
const ll mo=100000000;
ll a,n;
ll eulr(ll n){ll ret=n;for(int i=2;i*i<=n;i++)if(n%i==0){ret=ret/i*(i-1);while(n%i==0) n/=i;}if(n!=1) ret/n*(n-1);return ret;
}
ll powermod(ll a,ll b,ll mod){ if(!b) return 1;if(!a) return 0;ll test=1;for(int i=0;i<b&&test<mod;i++) test*=a;a%=mod;ll ans=1;while(b){if(b&1) ans=ans*a%mod;b>>=1;a=a*a%mod;}if(test>=mod) ans+=mod;return ans;
}
ll dfs(ll n,ll mod){if(n==1) return a%mod;ll phi=eulr(mod);return powermod(a,dfs(n-1,phi),mod);
}
int main()
{//cout<<powermod(4,2,100000)<<endl;while(scanf("%I64u%I64u",&a,&n)==2){printf("%I64u\n",dfs(n,mo)%mo);}return 0;
}
这篇关于hdu 3609 Up-up的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
