数论学习之起步篇（三）
1. 求解模线性方程
中国剩余定理有以下一组模线性方程，求xx≡b1(mod m1)x≡b2(mod m2) . . .x≡bn(mod mn)解为：x0≡(b1*M1*y1+b2*M2*y2+……+bn*Mn*yn) mod m 其中Mi=(m1*m2*m3*……*mn)/mi。而Mi*yi≡1(mod mi)#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<map>#include<queue>#include<stack>#include<vector>#include<ctype.h>#include<algorithm>#include<string>#define PI acos(-1.0)using namespace std;long long m[100],b[100],n;long long d,x,y;void ex_gcd(long long a, long long b, long long &d, long long &x, long long &y){ if (!b) { d=a; x=1; y=0; } else { ex_gcd(b,a%b,d,y,x); y-=(a/b)*x; }}long long chinaR(){ long long mm=1,a=0; int i; for (i=0; i<n; i++) mm*=m[i]; for (i=0; i<n; i++) { long long M=mm/m[i]; ex_gcd(M,m[i],d,x,y); a=(a+(x%mm)*M*b[i])%mm; } return (a%mm+mm)%mm;}int main (){ while(cin>>n) { if (!n) break; for (int i=0; i<n; i++) cin>>m[i]>>b[i]; long long a=chinaR(); cout<<a<<endl; } return 0;}