问题标题: 酷町堂:更相减损术

0
0

0
已采纳
黄依成
黄依成
中级天翼
中级天翼

just like 辗转相除法

0
曹灿阳
曹灿阳
初级天翼
初级天翼

有个函数是这样的:(超级方便!!!)

/*辗转相除法 
a=56,b=35,r=a%b;

    a       b       r(余数) 
    56      35      21(a%b)     
    35(a=b) 21(b=r) 14(a%b)
    21(a=b) 14(b=r) 7(a%b)
    14(a=b) 7(b=r)  0(a%b)
    7(a=b)  0(b=r)  ?
除到除数为0,此时被除数为两个数的最大公约数。
不需要考虑a和b的大小关系,辗转相除法会帮你自动更正为a>=b。 
*/ 
//核心代码: 
while(b!=0){
    r=a%b;
    a=b;
    b=r;
}
cout<<a;

 

我要回答