[NOI2002]荒岛野人

克里特岛以野人群居而著称。岛上有排列成环行的M个山洞。这些山洞顺时针编号为1,2,…,M。岛上住着N个野人，一开始依次住在山洞C1,C2,…,CN中，以后每年，第i个野人会沿顺时针向前走Pi个洞住下来。每个野人i有一个寿命值Li，即生存的年数。下面四幅图描述了一个有6个山洞，住有三个野人的岛上前四年的情况。三个野人初始的洞穴编号依次为1，2，3；每年要走过的洞穴数依次为3，7，2；寿命值依次为4，3，1。

奇怪的是，虽然野人有很多，但没有任何两个野人在有生之年处在同一个山洞中，使得小岛一直保持和平与宁静，这让科学家们很是惊奇。他们想知道，至少有多少个山洞，才能维持岛上的和平呢？

第1行为一个整数N(1≤N≤15)，即野人的数目。

第2行到第N+1每行为三个整数C_i, P_i, L_i (1≤C_i,P_i≤100, 0≤L_i≤10⁶ )，表示每个野人所住的初始洞穴编号，每年走过的洞穴数及寿命值

#include<cstdio> #include<algorithm> const int N=20; int n,s[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,y,x); y-=a/b*x; return d; } bool check(int m) { for(int i=1;i<=n;++i) for(int j=i+1;j<=n;++j) { int a=p[i]-p[j],b=m,c=s[j]-s[i],x,y; int d=exgcd(a,b,x,y); if(c%d) continue; a/=d,b/=d,c/=d; if(b<0) b=-b; x=(x*c%b+b)%b; if(x<=l[i]&&x<=l[j]) return 0; } return 1; } int main() { scanf("%d",&n); int mx=0; for(int i=1;i<=n;++i) scanf("%d%d%d",&s[i],&p[i],&l[i]),mx=std::max(mx,s[i]); for(int i=mx;;++i) if(check(i)) return printf("%d",i),0; return 0; }

详情