NOIP 2013提高组 同余方程若输入的是a,b那么gcd(a,b) 运算出了x,y使得ax+by=1我不明白为什么 (x mod 2b)mod b 就是题目解希望可以简单用数论证明

来源:学生作业帮助网 编辑:六六作业网 时间:2024/12/23 19:05:58
NOIP2013提高组同余方程若输入的是a,b那么gcd(a,b)运算出了x,y使得ax+by=1我不明白为什么(xmod2b)modb就是题目解希望可以简单用数论证明NOIP2013提高组同余方程若

NOIP 2013提高组 同余方程若输入的是a,b那么gcd(a,b) 运算出了x,y使得ax+by=1我不明白为什么 (x mod 2b)mod b 就是题目解希望可以简单用数论证明
NOIP 2013提高组 同余方程

若输入的是a,b

那么gcd(a,b) 运算出了x,y使得ax+by=1

我不明白为什么 (x mod 2b)mod b 就是题目解

希望可以简单用数论证明 


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了