记录编号	205930	评测结果	AAAAAAAAAA
题目名称	[NOIP 2012]同余方程	最终得分	100
用户昵称	<蒟蒻>我要喝豆奶	是否通过	通过
代码语言	C++	运行时间	0.028 s
提交时间	2015-11-05 20:29:28	内存使用	0.25 MiB

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int x,y;
int a,b;
int extended_euclid(int a, int b, int &x, int &y)// 扩展欧几里德算法,解gcd(a, b) = ax + by
{// 返回a,b的最大公约数
    if(b == 0) // gcd(a, b) == a
    {
        x = 1;
        y = 0;
        return a;
    }
    int n = extended_euclid(b, a%b, x, y);
    int tmp = x;
    x = y;
    y = tmp-(int)(a/b)*y;
    return n;
}
 
bool linear_equation(int a, int b, int c, int &x, int &y)
{
    int n = extended_euclid(a, b, x, y);
    if(c%n)return false;
    while(x<0)
    	x+=b;
    int k = c/n;
    x *= k;
    y *= k;
    return true;
}
int main()
{
	freopen("mod.in","r",stdin);
	freopen("mod.out","w",stdout);
	cin>>a>>b;
	linear_equation(a,b,1,x,y);// 结果存储在x,y中,用户调用时保证a、b、c都是整数
	cout<<x;
	return 0;
}