作业帮NOIP 2013提高组 同余方程
来源：学生作业帮 编辑：拍题作业网作业帮 分类：数学作业 时间：2024/04/26 21:16:51
NOIP 2013提高组 同余方程
若输入的是a,b
那么gcd(a,b) 运算出了x,y使得ax+by=1
我不明白为什么 (x mod 2b)mod b 就是题目解
希望可以简单用数论证明
首先求方程 ax+by=1中的x,y是扩展欧几里得算法,实际就是求的 ax mod b=1 这个问题
而这句话 (x mod d+d) mod d 与你说的 (x mod 2d) mod d 是不一样的
(x mod d+d) mod d 这样子写是主要x可能出现负数情况.运算过程先算mod,再算加法,而不是mod 2d
所以实际计算是 ((x mod d)+d) mod d
这样子负数就ok了
再问： 所求的x的绝对值难道一定没有b大吗 如果比b大了 x mod b 就不是x了
再答： 可以啊 ax + nb mod b = 1 也是成立的，但是这道题应该是求x最小的正数吧。
x，x+b，x+2b,.... 都是满足等式的，但是有个最小的不是？
而这句话 (x mod d+d) mod d 与你说的 (x mod 2d) mod d 是不一样的
(x mod d+d) mod d 这样子写是主要x可能出现负数情况.运算过程先算mod,再算加法,而不是mod 2d
所以实际计算是 ((x mod d)+d) mod d
这样子负数就ok了
再问： 所求的x的绝对值难道一定没有b大吗 如果比b大了 x mod b 就不是x了
再答： 可以啊 ax + nb mod b = 1 也是成立的，但是这道题应该是求x最小的正数吧。
x，x+b，x+2b,.... 都是满足等式的，但是有个最小的不是？