原题链接: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的最小正整数解t0,如果gcd(a,b)不能被c整除(表示无正整数解)或者求出的t0 > 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;
}