观察到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。

#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;
}

• 相关文章