https://ac.nowcoder.com/acm/contest/890/D

板子题套个好板子即可ac

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll __int128
 4 #define LL long long
 5 void exgcd(ll a,ll b,ll &g,ll &x,ll &y){
 6     if(!b){
 7         g=a;
 8         x=1;
 9         y=0;
10         return;
11     }
12     exgcd(b,a%b,g,y,x);
13     y-=(a/b)*x;
14 }
15 bool flag=false;
16 ll a1,a2,n1,n2;
17 void china(){
18     ll d=a2-a1;
19     ll g,x,y;
20     exgcd(n1,n2,g,x,y);
21     if(d%g==0){
22         x=((x*d/g)%(n2/g)+(n2/g))%(n2/g);
23         a1=x*n1+a1;
24         n1=(n1*n2)/g;
25     }
26     else flag=true;
27 }
28 LL mo[1005],a[1005];
29 ll realchina(int n){  
30     a1=a[1];
31     n1=mo[1];
32     for(int i=2;i<=n;i++){
33         a2=a[i];
34         n2=mo[i];
35         china();
36         if(flag)return -1;
37     }
38     return a1;
39 }
40 int n;
41 LL m;
42 int main(){
43     scanf("%d%lld",&n,&m);
44     for(int i=1;i<=n;i++){
45         scanf("%lld%lld",&mo[i],&a[i]);
46     }
47     ll ans=realchina(n);
48     if(ans>m)printf("he was probably lying\n");
49     else if(ans==-1)printf("he was definitely lying\n");
50     else printf("%lld\n",(LL)ans);
51 }