傳送門 因為本題數據范圍不大，所以考慮暴力枚舉。 我們可以用擴歐來判斷他們的最早相遇時間，若他們都活著，則不合法。 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)){新聞熱點
疑難解答
