题目链接

GCD and LCM Aizu - 0005

思路

$$ 最大公因数，最小共倍数模板题 $$

时间复杂度

$$ O(log max(a, b)) $$

代码

#include <cstdio>

using namespace std;

class NT {
public:
    long long gcd(long long a, long long b) {
        if (b == 0) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }

    long long lcm(long long a, long long b) {
        return a / gcd(a, b) * b;
    }
};

int main() {
    NT nt;
    int a, b;
    while (~scanf("%d%d", &a, &b)) {
        printf("%lld %lld\n", nt.gcd(a, b), nt.lcm(a, b));
    }

    return 0;
}