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

我的第一道数论紫题

首先,我们先看两个野人,他们相遇的充要条件是

\(C_i+P_i\times k\equiv C_j+P_j\times k\;(mod\;M)\) 其中\(k\)是第几年,且\(k\ge L_i\;and\;L_j\)

这个式子还是没有办法直接求解,我们对它进行如下变形

\(C_i+P_i\times k-C_j-P_j\times k=bM\)

\(k\times(P_j-P_i)+bM=C_i-C_j\)

令\(a=P_j-P_i,c=C_i-C_j\)

转化为\(ak+bM=c\)

用扩展欧几里得求解这个应该都知道吧

其中\(k,M\)是变量

我们对于每一个\(M\),只需要枚举每两个野人,只有他们对应的\(k\)都符合要求时,这个\(M\)便是可行的。

由于\(M\le10^6\)直接枚举即可\(AC\)

\(Code\)

#include <cstdio>
#include <iostream>
using namespace std;
const int maxn=20,maxm=1e6;
int l[maxn],p[maxn],c[maxn];
int n,m;
int exgcd(int a,int b,int &x,int &y)
{
if(!b) {x=1;y=0;return a;}
int ans=exgcd(b,a%b,x,y),t=x;
x=y;y=t-a/b*y;
return ans;
} bool check(int i,int j,int b)
{
int a=p[j]-p[i],d=c[i]-c[j],x,y;
if(a<0) a=-a,d=-d;
int gcd=exgcd(a,b,x,y);
if(d%gcd) return 1;
return ((x*(d/gcd)%(b/gcd)+(b/gcd))%(b/gcd))>min(l[i],l[j]);
} int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d%d",c+i,p+i,l+i),m=max(m,c[i]);
for(int i=m;i<=maxm;i++)
{
bool fg=1;
for(int j=1;j<=n&&fg;j++)
for(int k=1;k<=n&&fg;k++)
if(k!=j) if(!check(j,k,i)) fg=0;
if(fg)
{
printf("%d\n",i);
break;
}
}
return 0;
}
上一篇:bzoj1407 / P2421 [NOI2002]荒岛野人(exgcd)


下一篇:2017-05-4-C语言学习笔记