【bzoj1407】[Noi2002]Savage

2015.07.10 10:39 Fri | 37次阅读 | 旧日oi | 固定链接 | 源码

题目大意

有n个方程的参数c[i],p[i],l[i],要求对任意一对(i,j)1<=i<j<=n) 有c[i]+x*p[i]≡c[j]+x*pjmod m都无解。n<=15,m<=10^6
c[i]<=100,p[i]<=100.l[i]<=10^6,保证有解。

题解

嗯,题目大意已经把做法说完了是吧……
先从max(c[i])开始枚举m,对于每个m,再枚举每一对i,j,用扩展gcd求出(p[i]-p[j])*x+y*m=c[j]-c[i]的解,如果x有解并且最小的正整数解<=min(l[i],l[j]),那么就说明这个m不行了。
时间复杂度感觉不太靠谱啊,最坏情况要O(mn^2log(100)),但是能过这题。
细节的话就是gcd的时候每一项的正负什么的,还有注意long long的问题.

我的程序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define N 16
using namespace std;
int n,c[N],p[N],l[N];
void exgcd(int a,int b,int &x,int &y,int &d)
{
    if(!b){x=1;y=0;d=a;return;}
    exgcd(b,a%b,y,x,d);y-=a/b*x;
}
int main()
{
    //freopen("savage.in", "r", stdin);
    //freopen("savage.out", "w", stdout);
    cin>>n;
    int i,j,k=0,x,y,d,flag;
    for(i=1;i<=n;i++) scanf("%d%d%d",&c[i],&p[i],&l[i]),k=max(k,c[i]);
    for(;k<=1000000;k++)
    {
        flag=1;
        for(i=1;i<n&&flag;i++)
        for(j=i+1;j<=n;j++)
        {
            int a=p[i]>p[j]?p[i]-p[j]:p[j]-p[i];
            int b=p[i]>p[j]?c[j]-c[i]:c[i]-c[j];
            //if(b<0) b+=k;
            exgcd(a,k,x,y,d);
            if(b%d) continue;
            x=x*b/d;
            x=(x%(k/d)+(k/d))%(k/d);
            if(x>min(l[i],l[j])) continue;
            flag=0;break;
        }
        if(flag)
        {
            cout<<k<<endl;
            return 0;
        }
    }
}```