观察到n的范围极小,m的范围也才1000000。那就可以枚举答案了。
枚举答案M。满足对于任何(i,j),都满足C[i]+x*P[i]=C[j]+x*P[j](mod M)的最小正整数解x大于min(L[i],L[j]),或者不存在x。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll;ll An=0,c[20],p[20],l[20]; int n; ll ext_gcd(ll a,ll b,ll&x,ll&y){ if (!b){ x=1; y=0; return a;} ll xx,yy,d=ext_gcd(b,a%b,xx,yy); x=yy; y=xx-a/b*yy; return d; }ll equ(ll a,ll b,ll c){ ll x,y,d=ext_gcd(a,c,x,y); if (b%d) return -1; x*=b/d; while (x>c/d)x-=c/d; while (x<0) x+=c/d; return x; } int check(ll m){ for ( int i=1;i<n;i++) for ( int j=i+1;j<=n;j++){ ll d; if (p[i]>=p[j])d=equ(p[i]-p[j],c[j]-c[i],m); else d=equ(p[j]-p[i],c[i]-c[j],m); if (d!=-1&&d<=min(l[i],l[j])) return 1; } return 0; } int main(){ scanf ( "%d" ,&n); for ( int i=1;i<=n;i++) scanf ( "%lld%lld%lld" ,&c[i],&p[i],&l[i]),An=max(An,c[i]); for (;check(An);An++); printf ( "%lld\n" ,An); return 0; } |
2023年6月09日 13:55
edpost is a initiative of professional writers who have come together for dedicated news coverage of latest happenings around the country (India). Our team comprises of professional writers & citizen edpost.in journalists with diverse range of interest in Journalism who are passionate about publishing the Education Updates with transparency in general public interest.