A*B mod C的计算方法（转）
我的图书馆
A*B mod C的计算方法（转）
转自：方法一：大家都能想到，计算A*B的值，然后在计算A*B mod C的值。这是最简单的，但是这个有个弊端，即a*b的值不能太大，太大可能溢出。 方法二：回顾进制转换的知识，二进制转换为10进制可以以2的权值相加（貌似是这样描述的）。比如13=(*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=a%c;&&&&
while(b)&&&&
{&&&&&&&&&&
if(b&1)&&&
//根据2相应二进制位的值判断是否加A*2^n；因为有对b进行右移运算，所以每次只需判断最末位的结果就可以。&&&&&&&&&
{&&&&&&&&&&&&&&
result+=&&&&&&&&&&&&&&
if(result&=c)&&&&&&&&&&&&&&&&&
result-=c;&&&&&&&&
tmp&&=1; //计算 A*2^n的值。&&&&&&&&
if(tmp&=c)&&&&&&&&&&
tmp-=c;&&&&&
}&&} 方法三：乘法可以这样算：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){unsigned long long int a1=a,b1=b,c1=c;if(!a1)&&
return 0;&&&
return (((a1&1)*b1)%c1+(mul(a1&&1,b1,c1)&&1)%c1)%c1;}
发表评论：
TA的最新馆藏[转]&[转]&[转]&[转]&[转]&[转]&下载作业帮安装包
扫二维码下载作业帮
1.75亿学生的选择
(a*b)mod c= ((a mod c)*(b mod c)) mod c对么?如果不对就举个反例给我.
这个公式对的 ,用在大数上,以防溢出
为您推荐：
其他类似问题
扫描下载二维码}