九度OJ1085
时间：2014-03-05 17:50:12
收藏：0
阅读：526
说起这个题呢，就不得不提一种快速求解幂的算法——反复平方法，可以在O(logn)的复杂度完成求幂运算。具体思路我不说，巫泽俊大神翻译的《挑战程序设计竞赛》P123对此有详细描述。
但仅知道这个算法并不表示就能算出这道题，还需要一定的数学推理过程：
N=a0+a1*k+a2*k^2+……an*k^n
N‘=a0+a1+a2+……+an
N-N‘=a1*(k-1)+a2*(k-1)^2+a3*(k-1)^3+......+an*(k-1)^n
(N-N‘)%(k-1)=0
(N‘-N‘‘)%(k-1)=0
.....
(N(r-1)-N(r))%(k-1)=0
相加得(N-N(r))%(k-1)=0
N(r)=N%(k-1)
故(x^y)%(k-1)就是我们要求的。
当(x^y)%(k-1)=0时，注意结果为k-1
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 |
#include <stdio.h>#include<stdlib.h>typedef
long long ll;ll x,y,k;ll mod_pow(ll a,ll n,ll mod){ ll res=1; while(n>0) { if(n&1)res=res*a%mod; a=a*a%mod; n>>=1; } return
res;}int
main(){ while(scanf("%lld%lld%lld",&x,&y,&k)!=EOF) { ll num=mod_pow(x,y,k-1); if(num==0) printf("%lld\n",k-1); else printf("%lld\n",num); } return
0;} |
原文：http://www.cnblogs.com/wickedpriest/p/3581359.html
评论（0）