同余与模运算(数论初步) By ACReaper

93 阅读 0 评论 62 点赞

我是靠谱客的博主糟糕蜜蜂，最近开发中收集的这篇文章主要介绍同余与模运算(数论初步) By ACReaper，觉得挺不错的，现在分享给大家，希望可以做个参考。

First：

我们有如下公式:

(a + b) mod n = ((a mod n) + (b mod n) ) mod n;

(a - b) mod n = ((a mod n) - (b mod n) + n) mod n;

ab mod n = (a mod n)(b mod n)mod n

注意第二个表达式，因为a mod n - b mod n可能为负数，所以要加上n。记这三个公式不需要死记，

记住123456789 * 987654321如何求最后一位就够了，由这个我们可以推导出上面三个公式。

这边为了防止乘法溢出，可以这样用点小聪明（这是在n不超过long long或者_int64位时适用）

int mul_mod(int a,int b,int n){

a %= n, b %= n;

return (int )((long long )a * b % n);

}

以上就是糟糕蜜蜂为你收集整理的同余与模运算(数论初步) By ACReaper的全部内容，希望文章能够帮你解决同余与模运算(数论初步) By ACReaper所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。