2
9
2015
9
2015
NOIP提高组2012同余方程
这是一道水题：使用扩展欧几里得算法即可。
关于扩展欧几里得算法：
众所周知，欧几里得算法有这样的性质：gcd(a,b) = gcd(b,a mod b)；
而扩展欧几里得算法是用于解形如：ax+by = gcd(a,b) = k 的不定方程通解；
那么这样的通解存在且b∈N*时有：bx'+(a mod b) y' =gcd(a,b)同样有解；
由于 a mod b = a - [a/b]b，则原方程可化为：y'a+(x'-[a/b]y')b = gcd(a,b)；递归求解即可，复杂度O(log n)。
