首页 > 代码库 > BZOJ 1907 exgcd

BZOJ 1907 exgcd

2024-09-11 02:49:41   207人阅读

思路：

数据范围不大..

那我们就枚举M好了..

再两两判断一下有没有冲突

怎么判断呢？

exgcd!!!

 p[i]*k+c[i]=p[j]*k+c[j]  (mod m)

(p[j]-p[i])*k=c[i]-c[j](mod m)

(p[j]-p[i])*k+m*b=c[i]-c[j]

但是 gcd(c[i]-c[j],p[j]-p[i])不一定是1

我们就先搞出来 p[j]-p[i]和m 的gcd 记为tt

如果 c[i]-c[j]不是tt的倍数  ->无解

然后 就成了这个样子

(p[j]-p[i])*k+m*b=tt

两边同时乘一个c[i]-c[j]/tt

 

 求k的时候 mod的数 是(m/tt)

最后再判一判

复杂度是O(n2logn*M)（虽然复杂度不对 但是能卡过去   donno why）

//By SiriusRen#include <cstdio>#include <algorithm>using namespace std;int n,c[20],p[20],l[20],mx;int exgcd(int a,int b,int &x,int &y){    if(!b){x=1,y=0;return a;}    int tmp=exgcd(b,a%b,x,y),tt=x;    x=y;y=tt-a/b*y;return tmp;}bool solve(int m){    for(int i=1;i<=n;i++){        for(int j=i+1;j<=n;j++){            int k,b,t2=c[i]-c[j],tt=exgcd(((p[j]-p[i])%m+m)%m,m,k,b);            if(t2%tt)continue;            int tmp=t2/tt;            k=((k*tmp)%(m/tt)+(m/tt))%(m/tt);            if(k<=min(l[i],l[j]))return 0;        }    }return 1;}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++)scanf("%d%d%d",&c[i],&p[i],&l[i]),mx=max(mx,c[i]);    for(int i=mx;;i++)if(solve(i)){printf("%d\n",i);return 0;}}

 

BZOJ 1907 exgcd


联系
我们