转自:http://hi.baidu.com/ckh%5F0330/blog/item/2f6a711179f2b7f5c2ce79a8.html 方法一: 大家都能想到,计算A*B的值,然后在计算A*B mod C的值。这是最简单的,但是这个有个弊端,即a*b的值不能太大,太大可能溢出。
方法二: 回顾进制转换的知识,二进制转换为10进制可以以2的权值相加(貌似是这样描述的)。比如13=(1101)2=1*2^3+1*2^2+0*2^1+1*2^0。同样的,当我们计算A*B的时候,也可以将B化成2^n相加的式子。于是,我们可以将a*b mod c转换成[a*(2^b0+2^b1+……2^bn)] mod c=[a*2^b0+a*2^b1+……a*2^bn] mod c。利用公式(a+b)mod c=[(a mod c)+(b mod c)]mod c这个公式进行运算。
代码:
int mul(int a,int b,int c) { int result,tmp; tmp=a%c; while(b) { if(b&1) //根据2相应二进制位的值判断是否加A*2^n;因为有对b进行右移运算,所以每次只需判断最末位的结果就可以。 { result+=tmp; if(result>=c) result-=c; } tmp<<=1; //计算 A*2^n的值。 if(tmp>=c) tmp-=c; b>>=1; } return result; }
方法三: 乘法可以这样算:a*b=(a&1)*b+[(a>>1)*b]<<1。同时,有公式:(a+b)mod c=[(a mod c)+(b mod c)]mod c
unsigned long long mul(unsigned long long a,unsigned long long b,unsigned long long c) if(!a1) |
|