(a*b)%c 小的技巧

时间:2022-10-17 20:26:25

(a*b)%c这个问题看上去好简单啊。

当然我们不是来说这么简单的问题了。你想一想,我们会不会遇到这种情况,a是__int64 ,b也是__int64 当两个数足够大的时候我们直接相乘的就会出现__int64越界的情况,结果就会错误。

所以我们今天记录一下解决这样的问题的方法。不要让这些小的问题妨碍我们来做大的问题。

这里用到了2进制数,和位运算。当然不是转化。仅仅要你会能理解即可

我们先来这样处理。

1。我们分别将a,b对c取模。

2。这里不会的看一下有关位运算的知识。这里我也不知道该怎么说了,先看看程序吧。我把程序中的代码凝视加的好好的。

__int64 mult_mod(__int64 a,__int64 b,__int64 c)
{
a%=c;
b%=c;
__int64 ret=0;//ret记录终于的结果
while(b)//推断不是不是为0了
{
if(b&1)//假设b的二进制中的最后一位为1 那么加上a
{
ret+=a;ret%=c;
}
a<<=1;a%=c;//a随着b中二进制位数而扩大每次扩大两倍。
b>>=1;//b来缩小两倍 去掉最后一位 由于当前最后一位我们用完了,
}
return ret;
}

好了!

这个会二进制的应该一看就懂,不会的大概不好理解,我的表达能力有限,仅仅能这样了。

感谢自己坚持。