网站建设技术问题,腾讯企点打不开,十堰高端网站建设,个人网站可以做论坛吗?这篇文章讲介绍#xff1a;同余方程#xff0c;中国剩余定理
什么是同余方程#xff1f;
xy #xff08;mod p#xff09;这样的#xff0c;带同余号的式子就是同余方程。
什么是中国剩余定理#xff1f;
中国剩余定理#xff0c;顾名思义是出自中国#xff0c;它…这篇文章讲介绍同余方程中国剩余定理
什么是同余方程
xy mod p这样的带同余号的式子就是同余方程。
什么是中国剩余定理
中国剩余定理顾名思义是出自中国它最早在《孙子算经》中出现就是为了解决一类一元一次线性同余方程。
举个例子
有一个数对3取模为2对5取模为3对7取模为2 求这个数
写成同余方程就是 1x 2mod 3 2x 2mod 5 3x 2mod 7 我们需要去解这个同余方程组。 就需要用到中国剩余定理具体证明可以自查这里只给出结论
1x a1mod m1 2x a2mod m2 3x a3mod m3 ..... n: x an ( mod mn )
其中m1,m2,m3......mn两两互质第一步设Mm1*m2*m3*.......mn
第二步设 bi M / mi (整除
第三步设 inv(bi) bi^-1 (mod mi) (不是bi的倒数是bi模mi的逆元
利用 bi * invbi 1 mod mi 求出 invi 我们就可以得到x的通解 第四步x a1*b1*t1 a2*b2*t2…… an*bn*tn kM ;
代入上面的例子我们可以得到x23k*105
所以我们需要分成 四步来求 第一步累乘模数 Mm1*m2*……mn 第二步累乘结果除以对应模数 bi M/mi 第三步求bi模以mi的逆元 invbi 用费马小定理或exgcd 第四步求和 余数*逆元*模数之积/模数 k模数之积
也就是 x [从i0到in累加] ai*invbi*bi kM
所以我们就求出了x的通式子我们要算出最小正整数x应该咋办捏就直接M 在对M取模就行了嗷嗷嗷。 xxM%M
洛谷P1495 曹冲养猪 设其一共有x只母猪。 已知数据(为了套板子直接把数组名换成熟悉的 猪圈数m1m2m3m4……mn 剩余猪a1a2a3a4……an 也就是猪圈就是模数剩余猪就是余数。 也就有同余方程组 xa1 mod m1 xa2 mod m2 ……………… xanmod mn 接下来用中国剩余定理套板子即可 第一步求模数之积M m1*m2*m3……mn 第二步求模数之积除以当前模数biM/mi 第三步求bi模以mi逆元invbi 如何用exgcd求invbi 下面推公式 bi*invbi 1 mod mi bi*invbi y*mi 1 exgcdbimiinvbiy即可 数据保证 bi 与 mi 互质 第四步求和 x 求和ai*bi*invbikM 由于我们要求的是最小正整数的x所以直接套公式 xxai*bi*invbiM%M xx%Mai*bi*invbi%M M%M #define _CRT_SECURE_NO_WARNINGS
#includeiostream
#includecstdio
#includecmath
#includestring
#includecstring
#includestring
#includealgorithm
#includevector
#includecctype
#includemap
#includeset
#includequeue
#includenumeric
#includeiomanip
using namespace std;
typedef long long LL;
const int N 20;void exgcd(int a, int b, int x, int y) {if (b 0) {x 1, y 0;return;}exgcd(b, a % b, y, x);y - a / b * x;
}
LL M 1;
int inv[N], a[N], m[N];
LL b[N];
int t;
int main() {int n;cin n;for (int i 1; i n; i) {cin m[i] a[i]; // m为模数a为余数M * m[i]; // 求模数之积}LL x 0;for (int i 1; i n; i) {//求模数之积除以当前模数b[i] M / m[i];exgcd(b[i], m[i], inv[i], t);inv[i] (m[i] inv[i]) % m[i];while (a[i]--) {x (x inv[i] * b[i])%M;}}cout x;}
