作者在 2012-03-15 11:49:12 发布以下内容
先把b表示成二进制形式。
你可以想象一下假设a=3,b=7,c=2;
b的二进制代码简写为111，根据求模的公式c*d%e=(c%e*d%e)%e;
我们第一步把b转成二进制形式111，那么(a^b)%c={[(a^100)%c]*[(a^010)%c]*[(a^001)%c]}%c;
我们还会发现(a^100)%c=[(a^010)%c*(a^010)%c]%c;
a^010%c=[(a^001%c)*a^001%c]%c;
以下是代码
#include <stdio.h>
long mod(long a,long b,long c)
{
int i=0,d[500],n;
long mo=1,t;
while(b) //把b转换成二进制
{
d[i]=b&1;
b>>=1;
i++;
}
n=i;
if(d[0])
mo=a%c;
t=a;
for(i=1;i<n;i++) //核心代码，（仔细观察特殊数据t,mo的变化规律）
{
t*=t;
t%=c;
if(d[i]&1)
mo=mo* t%c;
}
return mo;
}
int main()
{
long a,b,c,n;
scanf("%ld",&n);
while(n--)
{
scanf("%ld%ld%ld",&a,&b,&c);
printf("%ld\n",mod(a,b,c));
}
return 0;
}
long mod(long a,long b,long c)
{
int i=0,d[500],n;
long mo=1,t;
while(b) //把b转换成二进制
{
d[i]=b&1;
b>>=1;
i++;
}
n=i;
if(d[0])
mo=a%c;
t=a;
for(i=1;i<n;i++) //核心代码，（仔细观察特殊数据t,mo的变化规律）
{
t*=t;
t%=c;
if(d[i]&1)
mo=mo* t%c;
}
return mo;
}
int main()
{
long a,b,c,n;
scanf("%ld",&n);
while(n--)
{
scanf("%ld%ld%ld",&a,&b,&c);
printf("%ld\n",mod(a,b,c));
}
return 0;
}