说起这个题呢,就不得不提一种快速求解幂的算法——反复平方法,可以在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
#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;
}