【线性模方程】BZOJ 1407 [Noi2002]Savage 题解

2019-04-13 20:33发布

站内文章 / 模拟电子
15307 0 1187

题目大意

n" role="presentation" style="position: relative;">n个人在m" role="presentation" style="position: relative;">m个点的环上，每个人初始在点ci" role="presentation" style="position: relative;">ci，能活Li" role="presentation" style="position: relative;">Li秒，每秒会向后走pi" role="presentation" style="position: relative;">pi步，求出最小的m" role="presentation" style="position: relative;">m使得任意两个人在有生之年都不会在一个点上相遇。

解题分析

转化一下这题，如果两个人i,j" role="presentation" style="position: relative;">i,j在第x" role="presentation" style="position: relative;">x天相遇了，说明什么？ ci+x∗pi≡cj+x∗pj(Mod m)" role="presentation" style="position: relative;">ci+x∗pi≡cj+x∗pj(Mod m) 转移 (pi−pj)x≡ci−cj(Mod m)" role="presentation" style="position: relative;">(pi−pj)x≡ci−cj(Mod m) 就是线性模方程，如果算出x无解（这辈子都碰不上）或x>min(Li,Lj)" role="presentation" style="position: relative;">x>min(Li,Lj)，则i,j" role="presentation" style="position: relative;">i,j一定碰不到，这样可以先找出一个m，再用n2" role="presentation" style="position: relative;">n2个方程来验证，但是这不满足二分，所以……穷举大法好（ans<=106" role="presentation" style="position: relative;">ans<=106）

示例程序

(传送门) #include #define LL long long using namespace std; int n; LL a[20],b[20],c[20],s,ans; inline void readL(LL &x){ x=0; char ch=getchar(); while ('0'>ch||ch>'9') ch=getchar(); while ('0'<=ch&&ch<='9') {x=x*10+ch-'0'; ch=getchar();} } void exgcd(LL a,LL b,LL &d,LL &x,LL &y){ if (!b) {d=a; x=1; y=0;} else {exgcd(b,a%b,d,y,x); y-=x*(a/b);} } bool _check(LL tem){ for (int i=1;ifor (int j=i+1;j<=n;j++){ LL C=((a[i]-a[j])%tem+tem)%tem,A=((b[j]-b[i])%tem+tem)%tem,g,x,y; exgcd(A,tem,g,x,y); if (C%g) continue; int m=tem/g,k=(x*C/g%m+m)%m; if (k<=c[i]&&k<=c[j]) return false; } return true; } int main() { freopen("savage.in","r",stdin); freopen("savage.out","w",stdout); scanf("%d",&n); s=0; for (int i=1;i<=n;i++){ readL(a[i]); readL(b[i]); readL(c[i]); s=(ss; } for (ans=s;;ans++) if (_check(ans)) {printf("%d",ans); break;} return 0; }

热门文章