传送门 因为本题数据范围不大，所以考虑暴力枚举。 我们可以用扩欧来判断他们的最早相遇时间，若他们都活着，则不合法。 ps：本题不能用二分。
#include<cmath>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;int o[20],e[20],x[20],n,d,xx,y;void exgcd(int a,int b,int &d,int &x,int &y){ if (!b){ d=a,x=1,y=0; } else{ exgcd(b,a%b,d,y,x); y-=x*(a/b); }}int ok(int m){ for (int i=1;i<n;i++) for (int j=i+1;j<=n;j++){ int dx=((x[j]-x[i])%m+m)%m; int de=((e[i]-e[j])%m+m)%m; exgcd(de,m,d,xx,y); if ((dx%d)!=0) continue; dx/=d; int mm=m/d; int k=(dx*xx%mm+mm)%mm; if (k<=o[i]&&k<=o[j]) return 0; } return 1;}int main(){ scanf("%d",&n); int ma=0; for (int i=1;i<=n;i++){ scanf("%d%d%d",&x[i],&e[i],&o[i]); ma=max(ma,x[i]); x[i]--; } for (;;ma++) if (ok(ma)){ PRintf("%d",ma); return 0; }}新闻热点
疑难解答
