这里用了合并的方法来解决问题。
————————————————
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include<iostream> #include<cstdio> #define ll long long using namespace std; int n; ll a1,r1,a2,r2,x,y,z; void gcd_extend(ll a,ll b,ll &x,ll &y) { if (b==0) { x=1;y=0; z=a; return; } gcd_extend(b,a%b,x,y); int t=x; x=y; y=t-y*(a/b); } int main() { while (scanf("%d",&n)!=EOF) { bool flag=false; for (int i=1;i<=n;i++) { if (i==1) scanf("%lld%lld",&a1,&r1);else scanf("%lld%lld",&a2,&r2); if (flag||i==1) continue; gcd_extend(a1,a2,x,y); ll c=r2-r1; if (c%z!=0) { flag=true; continue; } a2/=z; c/=z; x*=c; x=(x%a2+a2)%a2; r1=r1+x*a1; a1*=a2; } if (flag) printf("-1\n");else printf("%lld\n",r1); } return 0; } |
