求最大公约数有暴力法和辗转相除法
时间复杂度
暴力:O(N)
辗转相除法:O(2logN)
辗转相除法原理:
设c为A B 的最大公约数 则存在K1 K2 使 A=K1*c B=K2*c;
r为A模B r=A - K3*B;
r=K1*c-K3*k2*c;
r=(K1-K2*K3)*c;
所以A 和 B 的余数一定是最大公约数c的倍数
1 #include2 3 int gcd(int a, int b) 4 { 5 int temp, r; 6 if(a
本文共 314 字，大约阅读时间需要 1 分钟。
求最大公约数有暴力法和辗转相除法
时间复杂度
暴力:O(N)
辗转相除法:O(2logN)
辗转相除法原理:
设c为A B 的最大公约数 则存在K1 K2 使 A=K1*c B=K2*c;
r为A模B r=A - K3*B;
r=K1*c-K3*k2*c;
r=(K1-K2*K3)*c;
所以A 和 B 的余数一定是最大公约数c的倍数
1 #include2 3 int gcd(int a, int b) 4 { 5 int temp, r; 6 if(a
转载于:https://www.cnblogs.com/16-CHQ/p/6390503.html