算法学习之模线性同余方程组(中国剩余定理+求解同余方程组) poj1006+hdu3579

2019-04-14 08:16发布

站内文章 / 模拟电子
12136 0 901

中国剩余定理

中国剩余定理原文：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？ 解法：中国剩余定理描述的就是一元线性同余方程组(其中m1，m2，...，mn均互质)。
设 是整数m1,m2, ... ,mn的乘积，并设Mi是除了mi以外的n- 1个整数的乘积。
设为Mi模mi的逆元，所以有 将(S)的通解形式为 (这个式子想了半天才明白是怎么来的：依次模m1，m2，...，mn，就形成了(S)方程组了，因为有下列两个方程) ①
②
在模M意义下，(S)有唯一解 (以上来自百度百科) poj1006 题意：人生来就有三个生理周期，分别为体力、感情和智力周期，它们的周期长度为23天、28天和33天。每一个周期中有一天是高峰。现在给出三个日期对应于该天是体力、感情和智力的高峰。现在给你一个日期，求从这一天起过多少天三个高峰同时出现。 题解：中国剩余定理的运用，23，28和33两两互质。 代码(作为模板，复杂度O(n))： #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define debug cout<<"aaa"<

求解同余方程组

中国剩余定理就是在求解同余方程组，但是当除数两两不互质的情况。就不能用CRT的结论来解决。
还是这个方程组，现在取出其中两个方程：              x≡a1(mod m1)              x≡a2(mod m2) 转化为：              x+m1*x1=a1              x+m2*x2=a2 合并有：m1*x1+m2*x2=a1-a2 可以通过扩展欧几里德解出，若(a1-a2)%gcd(m1,m2)!=0，则无解 反之解出x1，带入x+m1*x1=a1，得到一个特解x0=a1-m1*x1。 通解x=x0+k*lcm(a1,a2)，即x≡x0(mod lcm(a1,a2)。 这样一来两个方程就合并成一个了，将这n个方程全部合并就可以解出x了。 hdu3579 题意：同中国剩余定理原文(这里除数两两不互质) 代码(作为模板，复杂度O(n))： #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define debug cout<<"aaa"< 留个模板
写的可能不太清楚嘿~

热门文章