【poj2891】Strange Way to Express Integers

题意：

给出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