[Noi2002]Savage

[Noi2002]Savage

数学题。

题解回去写(有个坑点)

flag++

#include <cstdio>

int n,m,c[25],p[29],l[29];

int exgcd(int a,int b,int &x,int &y){

	if(!b){x=1,y=0;return a;}

	int ans=exgcd(b,a%b,x,y),t=x;

	x=y,y=t-a/b*y;

	return ans;

}

int max(int a,int b){return a>b?a:b;}

int min(int a,int b){return a<b?a:b;}

int gcd(int a,int b){return b?gcd(b,a%b):a;}

bool check(int ans){

	int x,y;

	for(int i=1;i<=n;i++){

		for(int j=i+1;j<=n;j++){

			int b=ans,a=p[j]-p[i],C=c[i]-c[j],g=gcd(a,b);x=0,y=0;

			if(C%g==0){

				a/=g,b/=g,C/=g;

				exgcd(a,b,x,y);

				b=b<0?-b:b;

				x=(x*C%b+b)%b;

				if(!x) x+=b;

				if(x<=min(l[i],l[j]))return 0;

			}

		}

	}

	return 1;

}

int main(){

	int mx=-1;

	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 ans=mx;ans<=1e6;ans++)if(check(ans))return !printf("%d",ans);

}

巴特西

[Noi2002]Savage

最新文章

热门文章