比赛 防止浮躁的小练习v0.9 评测结果 AAAAAAAAA
题目名称 殉国 最终得分 72
用户昵称 jjky 运行时间 0.058 s
代码语言 C++ 内存使用 0.28 MiB
提交时间 2016-11-07 19:04:29
显示代码纯文本
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#define INF 3000000000000000000
using namespace std;
long long xx,yy,minn=INF,maxn=-1,sum;
long long exgcd(long long a,long long b,long long &x,long long &y)
{
	if(b==0)
	{
		x=1;
		y=0;
		return a;
	}
	long long d=exgcd(b,a%b,y,x);
	y-=x*(a/b);
	return d;
}
int main()
{
	freopen("BlackHawk.in","r",stdin);
	freopen("BlackHawk.out","w",stdout);
	long long a,b,c,x,y;
	cin>>a>>b>>c;
	long long d=exgcd(a,b,xx,yy);
	long long m=c/d,m_=c%d;
	long long x0=xx*m,y0=yy*m;
	c=c/d;
	b=b/d;
	a=a/d;
	long long l=-(x0/b),r=(y0/a);
	if(m_!=0||l>r)
		cout<<"-1"<<" "<<"-1"<<endl<<"0"<<endl;//x=x0+(b/(a,b))*t;y=y0-(a/(a,b))*t;
	else
	{
		if((r-l)>10)
		{
			for(long long i=l-1;i<=l+2;i++)
			{
				x=x0+b*i;
				y=y0-a*i;
				if(x>=0&&y>=0)
				{
					sum++;
					minn=min(x+y,minn);
					maxn=max(x+y,maxn);
				}
			}
			for(long long i=r-2;i<=r+1;i++)
			{
				x=x0+b*i;
				y=y0-a*i;
				if(x>=0&&y>=0)
				{
					sum++;
					minn=min(x+y,minn);
					maxn=max(x+y,maxn);
				}
			}
			sum+=(r-l-3);
		}
		else
		{
			for(long long i=l-1;i<=r+1;i++)
			{
				x=x0+b*i;
				y=y0-a*i;
				if(x>=0&&y>=0)
				{
					sum++;
					minn=min(x+y,minn);
					maxn=max(x+y,maxn);
				}
			}
		}
		if(sum==0)
			cout<<"-1"<<" "<<"-1"<<endl<<"0"<<endl;
		else
			cout<<minn<<" "<<maxn<<endl<<sum<<endl;
	}
	return 0;
}
/*
123456 123456789 12345678912345

*/