Sol:
根据题意可列方程:
(c[i] + x*p[i])%m = (c[j] + x*p[j])%m,即:c[i] + x*p[i] = c[j] + x*p[j] + y*m(x,y为未知数)
此问题就转换成一元二次方程求解了,扩展欧几里得(题目已经给了N , M的范围,所以只需枚举即可)。
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int maxn = 20 + 10; int n; int extend_gcd(int a,int b,int &x,int &y) { if(a==0&&b==0) return -1; if(b==0) { x=1; y=0; return a; } long long d=extend_gcd(b,a%b,y,x); y-=a/b*x; return d; } int C[maxn],P[maxn],L[maxn]; bool solve(int m) { for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { int x,y; int GCD=extend_gcd(P[j]-P[i],m,x,y); if((C[i]-C[j])%GCD) continue; x*=(C[i]-C[j])/GCD; if(GCD<0) GCD=-GCD; x=(x%(m/GCD)+m/GCD)%(m/GCD); if(x<=L[i]&&x<=L[j]) return false; } } return true; } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d",&n); int ans=0; for(int i=0;i<n;i++) { scanf("%d%d%d",&C[i],&P[i],&L[i]); ans=max(ans,C[i]); } while(!solve(ans)) ans++; printf("%d\n",ans); } return 0; }