萌新求助
查看原帖
萌新求助
315205
Kniqht楼主2023/11/5 14:38

就是说,a(x∗cd+kb)+b(y∗cd−ka)=ca(x*\frac{c}{d}+kb)+b(y*\frac{c}{d}-ka)=c 能表示出所有解,然后 k=1gcd⁡(a,b)k=\frac{1}{\gcd(a,b)} 时满足最小且为正整数。

但比如我们想得到的是 x′=(x∗cd+kb)x'=(x*\frac{c}{d}+kb) 最小,为什么一定是让这个 kbkb 最小,取模得到的余数就一定最小呢?是不是因为k=1gcd⁡(a,b)k=\frac{1}{\gcd(a,b)} 时 kbkb 最小,且若 kbkb 更大也一定是 k=bgcd⁡(a,b)k=\frac{b}{\gcd(a,b)} 的倍数,所以取模的数越小越好?

2023/11/5 14:38
加载中...