比赛 防止浮躁的小练习v0.9 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 殉国 最终得分 100
用户昵称 NVIDIA 运行时间 0.050 s
代码语言 C++ 内存使用 0.30 MiB
提交时间 2016-11-07 15:36:09
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y) 
{
	if(!a) 
	{
		x=0;
		y=1;
		return b;
	}
	ll d=exgcd(b%a,a,y,x);
	x-=b/a*y;
	return d;
	}
int main()
{
	freopen("BlackHawk.in","r",stdin);
	freopen("BlackHawk.out","w",stdout);
	ll a,b,c,x0,y0;
	scanf("%lld%lld%lld",&a,&b,&c);
	ll d=exgcd(a,b,x0,y0);
	if (c%d) 
	{
		printf("-1 -1\n0\n");
		return 0;
	}
	a/=d;
	b/=d;
	c/=d;
	x0*=c;
	y0*=c;
	ll W,Q;
	if (Q<W) 
	{
		printf("-1 -1\n0\n");
		return 0;
	}
	if (x0<0)
		W=(-x0+b-1)/b;
	else
		W=-x0/b;
	if (y0<0)
		Q=(y0-a+1)/a;
	else
		Q=y0/a;
	if(a>b)
		cout<<x0+y0+(b-a)*Q<<' '<<x0+y0+(b-a)*W<<endl<<Q-W+1<<endl;
	else
		cout<<x0+y0+(b-a)*W<<' '<<x0+y0+(b-a)*Q<<endl<<Q-W+1<<endl;
	return 0;
}
/*
#include <iostream>
using namespace std;

//扩展欧几里德算法
int ExGCD(int a, int b, int& x, int& y)
{
	if(b == 0)
	{
		x = 1, y = 0;
		return a;
	}
	int d = ExGCD(b, a%b, x, y);
	int temp = x;
	x = y;
	y = temp - a/b*y;
	return d;
}

int main()
{
	int x, y, d;
	d = ExGCD(99, 78, x, y);
	cout << d << " " << x << " " << y << endl;
	return 0;
}
*/