数论 - 同余与模算术

171 阅读 0 评论 113 点赞

我是靠谱客的博主温暖世界，这篇文章主要介绍数论 - 同余与模算术，现在分享给大家，希望可以做个参考。

(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 (在a大于b的情况下)
ab mod n = (a mod n)(b mod n) mod n

假如a * b，我们只求后结果俩位数，我们完全可以: (a%100)*(b%100)%100

大整数取模:
求n%m,(n <= 10¹⁰⁰, m <= 10⁹)
把大整数写成自左向右的形势，如 1234 = ((1*10 + 2) * 10 + 3) * 10 + 4然后每步取模。


string n;
int m;
cin >> n >> m;
int ans = 0;
for(int i = 0;i < n.size();i++)
ans = (ans*10 + (n[i]-'0')) % m;
cout << ans << endl;

模线性方程组:
输入a，b，n，求出: ax % n == b % n的解

该方程要成立那么肯定满足:(ax - b) % n == 0
那么就转化成 ax - b = ny (y为任意整数)
那么即: ax - ny = b，现在就转化成求整数解了，利用扩展欧几里得即可求出通式

以上就是温暖世界最近收集整理的关于数论 - 同余与模算术的全部内容，更多相关数论内容请搜索靠谱客的其他文章。

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