首页 > 代码库 > 中国剩余定理

中国剩余定理

2024-11-27 14:42:01   204人阅读

1079 中国剩余定理技术分享
基准时间限制：1 秒 空间限制：131072 KB 分值: 0 难度：基础题
技术分享 收藏
技术分享 关注
一个正整数K，给出K Mod 一些质数的结果，求符合条件的最小的K。例如，K % 2 = 1, K % 3 = 2, K % 5 = 3。符合条件的最小的K = 23。
 
Input
第1行：1个数N表示后面输入的质数及模的数量。（2 <= N <= 10)第2 - N + 1行，每行2个数P和M，中间用空格分隔，P是质数，M是K % P的结果。（2 <= P <= 100, 0 <= K < P)
Output
输出符合条件的最小的K。数据中所有K均小于10^9。
Input示例
32 13 25 3
Output示例
23

zhx大神讲过的方法：
大数翻倍法 ——来源于小学奥数
每次加前i个数的lcm，直至模第i个数是的结果是题目中的数
10^9要爆long long 的，数据弱A了
#include<cstdio>using namespace std;int n,a[11],b[11];long long get_gcd(long long a,long long b){    return !b ? a:get_gcd(b,a%b);}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);    long long ans=b[1];    long long lcm=a[1];    for(int i=2;i<=n;i++)    {        while(ans%a[i]!=b[i]) ans+=lcm;        long long gcd=get_gcd(lcm,(long long)a[i]);        lcm=lcm/gcd*(long long)a[i];    }    printf("%lld",ans);}

 

 

中国剩余定理  解法

       设m1，m2，m3 两两互素，则下面的同余方程组

　　x ≡ a1 mod m1

　　x ≡ a2 mod m2　　

　　……

　　x ≡ ak mod mk

　　令M=m1*m2*……mk

　　在0<=x<M 内有唯一解

　　记Mi=M/mi ,所以gcd（Mi，mi）=1，

       根据扩展欧几里得，一定存在整数x，y 满足 Mi*x+mi*y=1

　　（此时x为Mi在模mi意义下的逆元）

　　如果记ei=Mi*x，那么有 ：

               0  mod mj ，j≠i 

      ei ≡   1  mod mj ，j=i

       那么 e1*a1 + e2*a2 + ……ek*ak 是方程组的一个解

　　这个解 加减M的整数倍 可以得到最小非负整数解  

 

#include<cstdio>using namespace std;int n;int m[11],a[11];long long M=1,ans,Mi[11],e[11];void exgcd(long long a,long long b,long long &x,long long &y){    if(!b) x=1,y=0;    else { exgcd(b,a%b,y,x); y-=x*(a/b); }}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++) scanf("%d%d",&m[i],&a[i]),M*=m[i];    for(int i=1;i<=n;i++) Mi[i]=M/m[i];    long long x,y;    for(int i=1;i<=n;i++)     {        exgcd(Mi[i],m[i],x,y);        x=(x%m[i]+m[i])%m[i];        e[i]=Mi[i]*x%M;    }    for(int i=1;i<=n;i++) ans=(ans+e[i]*a[i])%M;    printf("%lld",ans);}

 

中国剩余定理


联系
我们