2010年清华大学计算机研究生机试真题

http://ac.jobdu.com/problem.php?pid=1085  求root(N, k)

/* N =a0+a1*k+a2*k^2+......ar*k^r; N'=a0+a1 +a2 +......ar; N-N' = a1(k-1)+a2(k^-1)+......+ar(k^r-1)右边提取k-1，可以得出结论：（N-N'）%(k-1)=0这样递推下去，（N-N'）%(k-1)=0 （N'-N''）%(k-1)=0 .... （N（r-1）-N（r））%(k-1)=0 直到N（r） < k所有式子相加(N - N(r))%(k-1)=0,N(r)是我们要求的结果...注意是求x^y%(k-1)，如果x^y%(k-1)==0，则输出k-1，否则输出x^y%(k-1) */ #include<iostream> #include<cstdio> using namespace std;inline long long mod_exp(long long x,long long y,int mod) //快速二分求幂(x^y)%mod { long long ans=1; while(y) { if(y&1) { ans*=x; if(ans>=mod) ans%=mod; } x*=x; if(x>=mod) x%=mod; y>>=1; } return ans; }int main(void) {int k;long long x,y,temp;while(scanf("%lld %lld %d",&x,&y,&k)!=EOF){temp = mod_exp(x,y,k-1);if(temp == 0)printf("%lld\n",k-1);elseprintf("%lld\n",temp);}return 0; }

总结

以上是生活随笔为你收集整理的2010年清华大学计算机研究生机试真题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。