ZigZagK的博客
[扩展欧几里得]BZOJ1407(Noi2002)【Savage】题解
2018年7月9日 13:34
BZOJ
查看标签

题目概述

有 $n$ 个JZ在一个长度为 $m$ 的环上,第 $i$ 个JZ刚开始在 $c_i$ ,每天会顺时针走 $p_i$ 的路程到那里虐人,共虐 $l_i$ 天。如果一个人在同一天被多个JZ虐了就会疯掉,这是JZ不想看到的(否则没人虐了)。问 $m$ 至少为多大使得没有人疯掉。

解题报告

$m$ 不满足单调性,所以爆枚 $m$ ,然后 $n^2$ 验证是否有两个JZ会在停止之前走到一起:

$$ c_i+p_ix\equiv c_j+p_jx\ (mod\ m)\Leftrightarrow (p_j-p_i)x\equiv c_i-c_j\ (mod\ m) $$

解同余方程得出最小的 $x$ ,然后判断 $x>l_i\ or\ x>l_j$ 。

ps: $m​$ 至少要是 $max\{c_n\}​$ ,被坑惨。

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=15;

int n,ans,c[maxn+5],p[maxn+5],l[maxn+5];

int exgcd(int a,int b,LL &x,LL &y) {if (!b) return x=1,y=0,a;int r=exgcd(b,a%b,y,x);return y-=a/b*x,r;}
inline bool check(int MOD){
    for (int i=1;i<n;i++)
        for (int j=i+1;j<=n;j++){
            int A=p[j]-p[i],C=c[i]-c[j],t;LL x,y;t=exgcd(A,MOD,x,y);if (C%t) continue;
            x=x*C/t%(MOD/t);if (x<0) x+=MOD/t;if (x<=l[i]&&x<=l[j]) return false;
        }
    return true;
}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    for (int i=(scanf("%d",&n),1);i<=n;i++)
        scanf("%d%d%d",&c[i],&p[i],&l[i]),ans=c[i]>ans?c[i]:ans;
    for (;ans<=1e6;ans++) if (check(ans)) break;
    return printf("%d\n",ans),0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!