记录编号	216451	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[ZLXOI 2015]殉国	最终得分	100
用户昵称	NVIDIA	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2015-12-29 09:10:45	内存使用	0.31 MiB

#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;
}

//定理一: 如果a,b是不都为0的任意整数,则d=gcd(a,b)是a,b的线性组合{ax+by: x,y∈Z}的最小元素.
// 已知d=gcd(a,b)=gcd(b,a mod b)
//
//由gcd(b,a mod b)得知,d = bx + a mod b = bx + (a-floor(a/b)*b)*y = a*y + b(x-floor(a/b)*y)
//当推到gcd(a,b)时,d′ = d = a*y + b(x-floor(a/b)*y)

//其他比较重要定理:
//定理二:d|a, d|b => d|(ax+by)  注:d|a表示a mod b == 0,即a能被b整除
//定理一推论: 对任意整数a,b如果d|a,d|b,则d|gcd(a,b)

//附:
int GCD(int a, int b)
{
  　　if(b == 0)
		　　return a;
	　　return GCD(b, a % b);
}
//迭代形式:
int GCD(int a, int b)
{
	while(b != 0)
	{
		int r = b;
		b = a % b;
		a = r;
	}
	return a;
}

*/