[NOI2002] 荒岛野人
link
二十年前的NOI是如此淳朴……
题并不难，主要是我对扩欧理解不深，再加上许久没写了，于是乎写得一塌糊涂……
考虑枚举洞穴个数 \(k\) ，并验证个数是否合法，很明显可以列出式子（假如两个野人 \(s\) 年后相遇）：
\[c_1+p_1s\equiv c_2+p_2s\pmod{k} \]变形可得：
\[(p_1-p_2)s-rk=c_2-c_1 \]可以发现这就是一个 \(a=p_1-p_2,b=k,c=c_2-c_1\) 的不定方程，需要判断的就是 \(x\) 是否比两个人的寿命都要短。
首先可以肯定的是 \(c\equiv0\pmod{\gcd(a,b)}\) 不成立时方程无解，那么野人永远不可能相遇，显然合法，接下来就考虑如何处理其他情况：
假设 \(g=\gcd(a,b)\) ，那么方程可以转化为 \(\frac{a}{g}x+\frac{b}{g}y=\frac{c}{g}\) ，其中 \(\gcd(a',b')=1\)。
\[a'x_0+b'y_0=1 \]此时应该先利用\(x_0,b'\)求出最小整数解之后再用以下公式。注意 \(b'<0\) 时要取相反数，否则求出来的东西会是负的。
\[a'(x_0c')+b'(y_0c')=c' \]最终的答案就是 \(x_0c'\) 。别的没什么了，就是要保证洞穴数要大于最大编号。
#include
#define zczc
#define int long long
const int N=105;
inline void read(int &wh){
wh=0;int f=1;char w=getchar();
while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();}
while(w<='9'&&w>='0'){wh=wh*10+w-'0';w=getchar();}
wh*=f;return;
}
int m,c[N],p[N],l[N];
int x,y;
inline int exgcd(int a,int b){
if(b==0){x=1,y=0;return a;}
int re=exgcd(b,a%b);
int xx=x,yy=y;
x=yy,y=xx-a/b*yy;
return re;
}
bool check(int wh){
for(int i=1;i