A^B mod C
Time Limit:1s | Memory limit:32M |
Accepted Submit:68 | Total Submit:376 |
Problem DescriptionInput
Output
Sample Input3 2 4 2 10 1000 Sample Output1 24 Original: FZU 2009 Summer Training IV--Number Theory |
解题:
强大的题目。需要考虑数据过大问题,数据处理过程中又可能有溢出。针对模取幂运算,收集转载一些很不错的文章。写在下一篇。(以下代码能过FZU 1650 ,但1650的代码不一定能通过1752这题。)
unsigned long long mul(unsigned long long a,unsigned long long b,unsigned long long c)
{
unsigned long long ret=0,tmp=a%c;
while(b)
{
if(b&0x1)
if((ret+=tmp)>=c)
ret-=c;
if((tmp<<=1)>=c)
tmp-=c;
b>>=1;
}
return ret;
}
unsigned long long mod(unsigned long long a,unsigned long long b,unsigned long long c)
{
unsigned long long y=1;
while(b)
{
if(b&1)
y=mul(y,a,c);
a=mul(a,a,c);
b=b>>1;
}
return y;
}
int main()
{
unsigned long long a,b,c;
while(scanf("%llu%llu%llu",&a,&b,&c)!=EOF)
printf("%llu/n",mod(a,b,c));
return 0;
}