当前位置:首页 > 数论 > 欧几里得 > 正文
SSOJ1377同余方程(NOIP2012)
3399+

题目大意:求关于 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。

最后稍微处理一下,如果出现负数就把他变成整数,如果太大就取余……

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,,,,

SSOJ1377同余方程(NOIP2012):等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!