FOJ1650-A^B mod C解题报告

新浪博客 发表时间 --2009-07-26 20:11:01

<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr> A^B mod C</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>

题解：

解法一：可套公式，A*B mod C=（（A mod C)*（B mod C) mod C ；A^B mod C=(A mod C)^(B mod C) mod C。

数据如果过大，则要考虑其他方法，此题的解法用到了逐次平方法（幂模运算）。具体实现过程参考数论相关的书籍。

<wbr></wbr>

需要注意的是，要小心溢出问题，比如a=a*b%c，如果简单这样计算的时候，如果a足够大的时候，就会导致溢出，处理方法为取a二进制值第一位乘以b与c模算加上a右移一位与相乘再和c做模运算后的值左移一位相加，再将相加的值和c做模运算，递归此过程，过程结束标志为a=0。

代码：

#include<stdio.h>

unsigned long long mul(unsigned long long a,unsigned long long b,unsigned long long c)
{
unsigned long long int a1=a,b1=b,c1=c;

if(!a1)
<wbr><wbr> return 0;<br><wbr><wbr><wbr> return (((a1&amp;1)*b1)%c1+(mul(a1&gt;&gt;1,b1,c1)&lt;&lt;1)%c1)%c1;<br> }</wbr></wbr></wbr></wbr></wbr>

unsigned long long mod(unsigned long long a,unsigned long long b,unsigned long long c)
{
<wbr><wbr> unsigned long long y=1;<br><wbr><wbr> while(b)<br><wbr><wbr> {<br><wbr><wbr><wbr><wbr><wbr> if(b%2==1)<br><wbr><wbr><wbr><wbr><wbr><wbr><wbr> y=mul(y,a,c);<br><wbr><wbr><wbr><wbr><wbr> a=mul(a,a,c);<br><wbr><wbr><wbr><wbr><wbr> b=b&gt;&gt;1;<br><wbr><wbr> }<br><wbr><wbr> return y;<br> }</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>

int main()
{
<wbr><wbr> unsigned long long a,b,c;<br><wbr><wbr> while(scanf("%llu%llu%llu",&amp;a,&amp;b,&amp;c)!=EOF)<br><wbr><wbr><wbr><wbr><wbr><wbr> printf("%llu\n",mod(a,b,c)%c);<br><wbr><wbr> return 0;<br> }</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>

解法二：

<wbr><wbr> 当数很大时比如快接近2的63次方时，解法一就不行，会溢出。要不溢出就得改变下解法一的mul函数，具体改变如下：</wbr></wbr>

<wbr><wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr>

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)
{
<wbr><wbr> if(b&amp;0x1)<br><wbr><wbr><wbr> if((ret+=tmp)&gt;=c)<br><wbr><wbr><wbr><wbr> ret-=c;<br><wbr><wbr><wbr> if((tmp&lt;&lt;=1)&gt;=c)<br><wbr><wbr><wbr><wbr> tmp-=c;<br><wbr><wbr><wbr> b&gt;&gt;=1;<br> }<br> return ret;<br> }</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>

这个函数是网上找的，现在是看不懂，研究中....

解法三：

代码：

#include "stdio.h"
int power(int a,int b,int c)
{
<wbr>int tmp;<br><wbr>if (b==0)<br><wbr>{<br><wbr><wbr>return 1;<br><wbr>}<br><wbr>tmp=power((a*a)%c,b/2,c);<br><wbr>if (b%2!=0)<br><wbr>{<br><wbr><wbr>tmp=(tmp*a)%c;<br><wbr>}<br><wbr>return tmp;<br> }<br> int main()<br> {<br><wbr>int a,b,c;<br><wbr>while(scanf("%d %d %d",&amp;a,&amp;b,&amp;c)!=EOF)<br><wbr>{<br><wbr><wbr>printf("%d\n",power(a,b,c));<br><wbr>}<br> }</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>