算法
暴力枚举+拓欧检查
思路
两个野人\(i\)与\(j\)会相遇,当且仅当方程\(c_i + xp_i \equiv c_j + xp_j(mod M)\)有正整数解且该解\(\leq min(l_i,l_j)\)。
又发现题目中保证 \(M \leq 1e6\),于是就可以愉快的暴力枚举了。
而上面的方程可以化为\(x(p_i - p_j) \equiv c_j - c_i(mod M)\),即求不定方程\((p_i - p_j)x + My = c_j-c_i\)的正整数解,可以使用拓展欧几里得定理。
复杂度:\(O(Mn^2logC_i)\)。
Tips
- \(M\)是不单调的,所以不能二分!
- \(M\)不能从\(1\)开始枚举,而要从\(max(c_i)\)开始,
毕竟每个野人都得有地方住。 - 要是不会拓欧的,可以康康这篇博客。
参考代码
#include <cstdio>
#include <algorithm>
using namespace std;
int n,ans;
struct Peo{
int c,p,l;
}p[20];
bool cmp(Peo x, Peo y){return x.p > y.p;}
int ex_gcd(int a, int b, int &x, int &y){
if(b == 0){
x = 1, y = 0;
return a;
}
int tmp = ex_gcd(b, a % b, x, y);
int ret = x - (a / b) * y;
x = y, y = ret;
return tmp;
}
int main(){
int Max = 0;
scanf("%d", &n);
for(int i = 1; i <= n; ++ i)
scanf("%d%d%d", &p[i].c, &p[i].p, &p[i].l), Max = max(Max, p[i].c);
sort(p + 1, p + 1 + n, cmp);
for(ans = Max; ans <= ((int)1e6 + 10); ++ ans){
int flag = 1;
for(int i = 1; i < n; ++ i){
for(int j = i + 1; j <= n; ++ j){
int a = p[i].p - p[j].p, b = ans, c = p[j].c - p[i].c, x = 0, y = 0;
int val = ex_gcd(a, b, x, y);
if(c % val != 0) continue;
int minn = (c / val * x % (b / val) + b / val) % (b / val);
if(minn <= min(p[i].l, p[j].l)){
flag = 0;
break;
}
}
if(!flag) break;
}
if(flag) return printf("%d\n", ans), 0;
}
return 0;
}