题解 P2421 【[NOI2002]荒岛野人】

题解在博客[食用](https://www.cnblogs.com/YoungNeal/p/9251301.html)效果更佳哦~ ## Solution 注意到答案不大于 $10^6$，考虑从小到大枚举答案。 对于枚举的一个答案 $ans$，我们希望对于每个满足 $c_i+k\times p_i\equiv c_j+k\times p_j\;(mod\;ans)$ 的 $k$ ,都要 $k>\min(l[i],l[j])$ 于是可以 $\mathcal {O(n^2)}$ 的枚举点对判断。 如何判断呢？再推一下式子： $$c_i+k\times p_i=c_j+k\times p_j+m\times ans$$ $$k\times(p_i-p_j)+m\times ans=c_j-c_i$$ 于是式子就愉快的变成了 $exgcd$ 标准形式。 然后求 $k$ 就好了。 ps：注意如果无解并不代表不满足情况，反而是满足情况。因为无解就是这俩货这辈子都碰不上面，显然合法。 ## Code ```cpp #include<cstdio> #include<cctype> #define N 20 #define min(A,B) ((A)<(B)?(A):(B)) #define max(A,B) ((A)>(B)?(A):(B)) 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 d=exgcd(b,a%b,x,y); int t=x; x=y; y=t-a/b*y; return d; } signed main(){ scanf("%d",&n);int mx=0; for(int i=1;i<=n;i++){ scanf("%d%d%d",&c[i],&p[i],&l[i]); mx=max(mx,c[i]); } for(int ans=mx;;ans++){ bool flag=0; for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ int x,y; int k=p[i]-p[j]; k=(k%ans+ans)%ans; int g=exgcd(k,ans,x,y); if((c[j]-c[i])%g) continue; x*=(c[j]-c[i])/g; int mo=ans/g; x=(x%mo+mo)%mo; if(x<=min(l[i],l[j])){ flag=1; break; } } if(flag) break; } if(flag) continue; printf("%d",ans); return 0; } } ```