洛谷题单指南-进阶数论-P2421 [NOI2002] 荒岛野人

原题链接：https://www.luogu.com.cn/problem/P2421

题意解读：一个环形坐标轴，n个点初始位于C1、C2...Cn，每个点每次逆时针移动P1、P2...Pn步，每个点分别最多只能移动L1、L2...Ln步，要求n个点能移动的点每次同时移动，且不能有任意两个点相遇，求满足要求的环形坐标轴最小的长度。

解题思路：

要求环形坐标轴的最小长度，不妨从小到大枚举这个长度，设为m

要求不能有任意两点相遇，可以枚举任意两点i，j在移动t次之后的位置，那么

应该有(Ci + Pi * t) % m != (Cj + Pj * t) % m，

转化成等式表达，即(Ci + Pi * t) % m = (Cj + Pj * t) % m 在t <= min(Li, Lj)时没有正整数解

进一步转化，设未知数s，Ci + Pi * t + m * s = Cj + Pj * t 在t <= min(Li, Lj)时没有正整数解

移项：(Pi - Pj) * t + m * s = Cj - Ci，另a = |Pi - Pj|, b = m, c =  (Pi > Pj ? 1 : -1) * (Cj - Ci)

用扩展欧几里得算法求a * t + b * s = c的关于t的最小正整数解t₀，如果gcd(a,b)不能被c整除（表示无正整数解）或者求出的t₀ > min(Li, Lj)则表示满足要求。

如果所有的点对都满足要求，则此时的m即为答案。

不难发现，对于每两个点的处理就是P1516青蛙的约会

100分代码：

#include <bits/stdc++.h>
using namespace std;const int N = 20, M = 1000000;int C[N], P[N], L[N];
int maxc;
int n;int exgcd(int a, int b, int &x, int &y)
{if(b == 0){x = 1, y = 0;return a;}int d = exgcd(b, a % b, y, x);y -= a / b * x;return d;
}int main()
{cin >> n;for(int i = 1; i <= n; i++) {cin >> C[i] >> P[i] >> L[i];maxc = max(maxc, C[i]);}for(int m = maxc; m <= M; m++){int yes = true;for(int i = 1; i < n; i++){for(int j = i + 1; j <= n; j++){int a = abs(P[i] - P[j]);int b = m;int c = (P[i] > P[j] ? 1 : -1) * (C[j] - C[i]);int t, s;int d = exgcd(a, b, t, s);if(c % d) continue;t *= (c / d);t = (t % (b / d) + b / d) % (b / d); //t的最小正整数解if(t > min(L[i], L[j])) continue;yes = false;break;}if(!yes) break;}if(!yes) continue;cout << m;break;}return 0;
}