【BZOJ 1407】 [Noi2002]Savage

Description

Input

Output

Sample Input

Sample Output

枚举+扩展欧几里得

（一开始以为满足二分性，实际并不满足，反例很好举）

为了取模方便，把山洞的标号都-1，使之从0开始。

枚举山洞个数为m，判断是否可行：

xi是初始山洞，ei是每年走过的山洞数，oi是野人的年龄

对于任意两个野人，计算出他们相遇需要的年数k：

xi+ei*k=xj+ej*k  (mod m)

(ej-ei)*k=xi-xj  (mod m)

只要该方程有解，且解<=oi,<=oj那么m就不成立。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#define inf 0x3f3f3f3f
#define LL long long
using namespace std;
int o[20],e[20],x[20],n;
int d,xx,y;
void exgcd(int a,int b,int &d,int &x,int &y)
{
	if (!b)
	{
		d=a,x=1,y=0;
	}
	else
	{
		exgcd(b,a%b,d,y,x);
		y-=x*(a/b);
	}
}
int ok(int m)
{
	for (int i=1;i<n;i++)
		for (int j=i+1;j<=n;j++)
		{
			int dx=((x[j]-x[i])%m+m)%m,de=((e[i]-e[j])%m+m)%m;
	        exgcd(de,m,d,xx,y);
			if ((dx%d)!=0) continue;
			dx/=d;
			int mm=m/d;
			int k=(dx*xx%mm+mm)%mm;
			if (k<=o[i]&&k<=o[j])
				return 0;
		}
	return 1;
}
int main()
{
    scanf("%d",&n);
	int ma=0;
	for (int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&x[i],&e[i],&o[i]);
		ma=max(x[i],ma);
		x[i]--;
	}
	for (int i=ma;;i++)
		if (ok(i))
		{
			cout<<i<<endl;
			return 0;
		}
	return 0;
}

感悟：

1.形如ax=b (mod c)可以转化为ax+cy=b  (mod c)，然后a,b,c同时mod gcd(a,c)再求

【BZOJ 1407】 [Noi2002]Savage

原文：http://blog.csdn.net/regina8023/article/details/44625467