中國剩余定理

Chinese remainder theorem

一個正整數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。

Sample Input

3 2 1 3 2 5 3

Sample Output

23 #include<cstdio> using namespace std; typedef long long ll; const int maxn=1e9+7; //擴展歐幾里得定理 ll ex_gcd(ll a,ll b,ll &x,ll &y) {ll d=a;if(!b) x=1,y=0;else{d=ex_gcd(b,a%b,y,x);y-=a/b*x;}return d; }//中國剩余定理 //x%m[i]=a[i] ll china(int n,int *a,int *m) {ll M=1,x=0,y,z;for(int i=0;i<n;i++)M*=m[i];for(int i=0;i<n;i++){ll M_i=M/m[i];ex_gcd(M_i,m[i],y,z);//M_i*y = 1(mod m[i])x = (x+M_i*a[i]*y)%M;}return (x+M)%M; } int main() {int n;//輸入的質數及模的數量while(scanf("%d",&n)!=EOF){int *m=new int[15];//質數int *a=new int[15];//K%m[i]=a[i]for(int i=0;i<n;i++){scanf("%d%d",&m[i],&a[i]);}printf("%lld\n",china(n,a,m));}return 0; }

?

總結

以上是生活随笔為你收集整理的51Nod1079 中国剩余定理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。