荒岛野人

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1496 字

求最小山洞数M，使得任意两野人在有生之年内都

一本通
练习

正文

/*
原题：「一本通 6.4 练习 1」荒岛野人（NOI 2002）
题意：求最小山洞数 M，使得任意两野人在有生之年(寿命 L_i、L_j)内都不在同一山洞相遇。
思路：M 从 max(C_i) 递增枚举；对每对野人 i,j，相遇方程 (P_i-P_j)·t ≡ C_j-C_i (mod M)，用扩展欧几里得求最小非负解 t，若 t≤min(L_i,L_j) 说明会在生前相遇，则该 M 不可行。
复杂度：枚举 M 上限约 1e6，每对 O(log M)，总体 O(N^2·M·log M)。
易错点：M 至少为 max(C_i)；相遇时 t 可为 0（初值同洞）；用扩展欧几里得判定可解性并取最小非负解再与寿命比较。
*/
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1;y=0;
        return a;
    }
    ll x1,y1;
    ll g=exgcd(b,a%b,x1,y1);
    x=y1;
    y=x1-(a/b)*y1;
    return g;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    if(!(cin>>n))return 0;
    vector<int> C(n),P(n),L(n);
    int mx=0;
    for(int i=0;i<n;i++){
        cin>>C[i]>>P[i]>>L[i];
        if(C[i]>mx)mx=C[i];
    }
    // 从 max(C_i) 开始枚举 M
    for(int M=mx;;M++){
        bool ok=true;
        for(int i=0;i<n&&ok;i++){
            for(int j=i+1;j<n&&ok;j++){
                // (P_i-P_j)·t ≡ C_j-C_i (mod M)
                ll a=P[i]-P[j];
                ll b=C[j]-C[i];
                ll m=M;
                ll x0,y0;
                ll g=exgcd(a,m,x0,y0);
                if(b%g!=0)continue;          // 无解 => 永不相遇
                ll mg=m/g;
                x0=((x0%mg)+mg)%mg;
                x0=(__int128)x0*(b/g)%mg;    // 最小非负解 t
                if(x0<=min(L[i],L[j]))ok=false;  // 生前相遇
            }
        }
        if(ok){
            cout<<M<<'\n';
            return 0;
        }
    }
    return 0;
}

荒岛野人

正文

一本通·提高篇的其它内容