1 //Accepted    164 KB    16 ms 2 //拓展欧几里得 3 //m=a1*x+b1  --（1） 4 //m=a2*(-y)+b2 --（2） 5 //->a1*x+a2*y=b2-b1 6 //由欧几里得算法可得上式的解 7 //由a*x+b*y=gcd(a,b) 8 //可得a(x+b)+b(y-a)=gcd(a,b) 9 //所以最小正整数解x=(x%b+b)%b;10 //现考虑由（1）（2）两式得到的解m11 //有x=m mod (a1*a2/gcd(a1,a2))12 //m是最小正整数解，m+a1*a2/gcd(a1,a2)也是（1）（2）的解13 #include <cstdio>14 #include <cstring>15 #include <iostream>16 using namespace std;17 __int64 extend_gcd(__int64 a,__int64 b,__int64 &x,__int64 &y)18 {19     if (b==0)20     {21         x=1;22         y=0;23         return a;24     }25     __int64 r=extend_gcd(b,a%b,x,y);26     __int64 t=x;27     x=y;28     y=t-a/b*y;29     return r;30 }31 int main()32 {33     int n;34     while (scanf("%d",&n)!=EOF)35     {int flag=0;36     __int64 a1,b1,a2,b2;37     __int64 x,y,c,d;38     scanf("%I64d%I64d",&a1,&b1);39     for (int i=2;i<=n;i++)40     {41         scanf("%I64d%I64d",&a2,&b2);42         if (flag) continue;43         d=extend_gcd(a1,a2,x,y);44         c=b2-b1;45         if (c%d)46         {47             flag=1;48         }49         else50         {51             __int64 p=a2/d;52             x=(c/d*x%p+p)%p;53             b1=a1*x+b1;54             a1=a1/d*a2;55         }56     }57     if (flag) printf("-1\n");58     else printf("%I64d\n",b1);59     }60     return 0;61 }