又是一道扩欧的题。
要求一个最小的m使得 Ci+Pi*x≡Cj+Pj*x mod m(i!=j) 在x在第i个人和第j个人的有生之年无解。
也就是 (Pi-Pj)*x+m*y=Cj-Ci 在min(Li,Lj)上无解。
题目限制了保证有解且m<=1e6，那么可以考虑枚举m，在暴力地对每个人进行判断。
理论最差复杂度为1e6*n^2^log，但实际上远达不到这种情况。
需要注意的是m必须大于等于max(Ci)。
#include<complex> #include<cstdio> using namespace std; const int N=21; int n; int C[N],P[N],L[N]; int Exgcd(int a,int b,int &x,int &y) { if(!b) { x=1;y=0; return a; } int r=Exgcd(b,a%b,x,y),tmp=x; x=y;y=tmp-a/b*y; return r; } bool check(int m) { for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) { int x,y,a=abs(P[i]-P[j]),b=m,c=P[i]-P[j]>0?C[j]-C[i]:C[i]-C[j]; int r=Exgcd(a,b,x,y); if(c%r==0) if((x*(c/r)%(b/r)+(b/r))%(b/r)<=min(L[i],L[j])) return 0; } return 1; } int main() { scanf("%d",&n); int l=0; for(int i=1;i<=n;i++) { scanf("%d%d%d",&C[i],&P[i],&L[i]); l=max(l,C[i]); } for(int i=l;i<=1000000;i++) if(check(i)) { printf("%d\n",i); break; } return 0; }
原文：https://www.cnblogs.com/LeTri/p/9152681.html