SSOJ1377同余方程（NOIP2012）
4272+
作者：crxis 发布：2017-07-11 分类：欧几里得
题目大意：求关于 x 同余方程 ax ≡ 1 (mod b)的最小正整数解。
输入
输入只有一行，包含两个正整数 a, b，用 一个 空格隔开。
输出
输出只有一行包含一个正整数x，即最小正整数解，输入数据保证一定有解。
样例输入
3 10
样例输出
7
提示
【数据范围】
对于 40% 的数据， 2 ≤b≤ 1,000 ；
对于 60% 的数据， 2 ≤b≤ 50,000,000
对于 100% 的数据， 2 ≤a, b≤ 2,000,000,000
NOIP2012提高组第二天第一题
解题思路
a*x % b = 1，不妨设y = – a*x / b，那么a*x + b*y = 1，现在要求的是最小正整数x。
利用欧几里得法求最大公约数，得到最大公约数时b = 0，且此时a = 1。那么a*x + b*y = 1的一个可行解是x = 1，y = 0。
现在考虑如何求回去：不妨设a/b = q，a%b = r，则a = b*q + r；又a*x + b*y = 1，消去a可得b*(qx+y) + r*x = 1。
为了区分递归的两层x、y，上一层用x和y来表示，下一层用x’和y’来表示，即x’ = (qx+y)，y’ = x，也即x = y’ ，y = x’ – qx。现在由下一层可知x’ 和y’ ，可以算出x和y。
最后稍微处理一下，如果出现负数就把他变成整数，如果太大就取余……
程序实现
