51 Nod 1079 中国剩余定理（孙子定理）NOTE:互质情况

时间：2023-02-05 22:59:34

1079 中国剩余定理

一个正整数K，给出K Mod 一些质数的结果，求符合条件的最小的K。例如，K % 2 = 1, K % 3 = 2, K % 5 = 3。符合条件的最小的K = 23。

收起

输入

第1行：1个数N表示后面输入的质数及模的数量。（2 <= N <= 10)

第2 - N + 1行，每行2个数P和M，中间用空格分隔，P是质数，M是K % P的结果。（2 <= P <= 100, 0 <= K < P)

输出

输出符合条件的最小的K。数据中所有K均小于10^9。

输入样例

3

2 1

3 2

5 3

输出样例

23

孙子定理

例：求符合kk%a=2,kk%b=3,kk%c=5的最小kk.

ans=bc*i+ac*j+ab*k;

以a为例：ans%a=bc*i%a=2(另外两个都是a的倍数)

        (bc*x)%a=1;//bc*x=a*y+1拓展欧几里得定理求解

        2%a=2;

        bc*i%a=(bc*x)*2%a=2;//乘数之余等于余数之乘

则ans=(bc*x1)*2+(ac*x2)*3+(ab*x3)*5; 解kk=ans%(abc);   
#include<iostream>

#define ll long long

using namespace std;

ll a[13],b[13];

void exgcd(ll m,ll n,ll &x,ll &y)

{

        if(!n){

                x=1;y=0;

                return ;

        }

        exgcd(n,m%n,x,y);

        ll tmp=x;

        x=y;//x=y2

        y=tmp-(m/n)*y;//y1=x2-(m/n)*y2

}

int main()

{

        int n;

        ll sum=1;

        scanf("%d",&n);

        for(int i=0;i<n;i++)

                scanf("%lld%lld",&a[i],&b[i]),sum*=a[i];

        ll ans=0;

        for(int i=0;i<n;i++){

                ll x,y;

                ll m=sum/a[i];

                exgcd(m,a[i],x,y);//m*x=a[i]*y+1;

                ans=(ans+m*b[i]*x)%sum;

        }

        if(ans<0)

                ans+=sum;

        printf("%lld\n",ans%sum);

        return 0;

}

相关文章