NOI2002荒岛野人Savage
Description
Input
第1行为一个整数N(1<=N<=15)，即野人的数目。第2行到第N+1每行为三个整数Ci, Pi, Li (1<=Ci,Pi<=100, 0<=Li<=106 )，表示每个野人所住的初始洞穴编号，每年走过的洞穴数及寿命值。
Output
仅包含一个数M，即最少可能的山洞数。输入数据保证有解，且M不大于106。
Sample Input
3
1 3 4
2 7 3
3 2 1
1 3 4
2 7 3
3 2 1
Sample Output
6
该样例对应于题目描述中的例子。
题解
枚举m>=max{c[i]}
使得对于每一对i，j
有c[i]+x*p[i]=c[j]+x*p[j] (mod m)
无解或者最小正整数解>min(l[i],l[j])
上式可以用exgcd求解
即（p[i]-p[j]）*x-my=c[j]-c[i]
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x*=10;x+=ch-'0';ch=getchar();} return x*f; } int n,mx; int C[20],p[20],l[20]; int gcd(int a,int b){return b==0?a:gcd(b,a%b);} void exgcd(int a,int b,int &x,int &y) { if(b==0){x=1;y=0;return;} exgcd(b,a%b,x,y); int t=x;x=y;y=t-a/b*y; } bool jud(int m) { int a,b,c,t,x,y; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) { a=p[i]-p[j],b=m,c=C[j]-C[i]; t=gcd(a,b); if(c%t==0) { a/=t;b/=t;c/=t; exgcd(a,b,x,y); b=abs(b); x=((c*x)%b+b)%b; if(!x)x+=b; if(x<=min(l[i],l[j]))return 0; } } return 1; } int main() { n=read(); for(int i=1;i<=n;i++) C[i]=read(),p[i]=read(),l[i]=read(),mx=max(C[i],mx); for(int i=mx;;i++) if(jud(i)){printf("%d",i);return 0;} } |
计数器 9793301
OI 课件=>
OI 课件=>
虐NOI
副队又D我T T