首页 > 代码库 > (a*b)%c 小的技巧

(a*b)%c 小的技巧

(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;
}

好了!

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

感谢自己坚持。