题意：
给出n个模方程x=a(mod r) 求x的最小解
题解：
这就是个线性模方程组的模版题- – 但是有一些要注意的地方
extgcd算出来的解x可能负数 要让x=(x%mo+mo)%mo
而且mo不是等于lcm(r1,r2) 而是r2/gcd(r1,r2)
代码：
1 #include <cstdio> 2 typedef long long ll; 3 ll n,a,r; 4 ll extgcd(ll &x,ll &y,ll a,ll b){ 5 if (!b){ 6 x=1,y=0; 7 return a; 8 }else{ 9 ll res=extgcd(x,y,b,a%b); 10 ll t=x; 11 x=y; 12 y=t-a/b*y; 13 return res; 14 } 15 } 16 int main(){ 17 while (scanf("%I64d",&n)!=EOF){ 18 scanf("%I64d%I64d",&r,&a); 19 ll x,y,a1,r1; 20 bool bo=1; 21 for (ll i=2;i<=n;i++){ 22 scanf("%I64d%I64d",&r1,&a1); 23 ll gc=extgcd(x,y,r,r1); 24 if ((a1-a)%gc) bo=0; 25 ll mo=r1/gc; 26 x=(x*(a1-a)/gc%mo+mo)%mo; 27 a+=r*x; 28 r*=r1/gc; 29 } 30 if (!bo) puts("-1"); 31 else printf("%I64d ",a); 32 } 33 }
View Code