试除法求约数
以x/i为分界点,只找较小的数即可。
1 | #include "iostream" |
求最大公约数
基本原理:辗转相除法
约定a是较大数b是较小数。
a和b的公约数与b和a%b的公约数相等
1 | 辗转相除法运用了分块的思想,比如我们想要求88和48的最大公约数,先求88%48=40;88=48+40;如果我们求出48和12的最大公因数,就求出了64和48的最大公因数;以此类推要求出48和40的的最大公因数,48=40+8,求出40和8的最大公因数就是48和40的最大公因数,也就是88和48的最大公因数,按照这种方式知道a%b=0;b就是最终的结果; |
1 | #include "iostream" |
本文作者: jiangyuhao
本文链接: http://example.com/2022/03/01/%E7%BA%A6%E6%95%B0/
版权声明: 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!