#52077: c++詳解(含原理)


11155088@gs.hs.ntnu.edu.tw (ace1110)

學校 : 不指定學校
編號 : 298370
來源 : [118.169.28.170]
最後登入時間 :
2025-09-24 21:58:03

a*b = gcd(a, b)*lcm(a, b)

#include <iostream>
#include <vector>
#include <numeric>
#include <cmath>

using bigint = long long;

bigint gcd(bigint a, bigint b) {
    while (b != 0) {
        bigint temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    int T;
    std::cin >> T;
    while (T--) {
        bigint G, L;
        std::cin >> G >> L;

        if (L % G != 0) {
            std::cout << -1 << std::endl;
            continue;
        }

        bigint product = L / G;
        bigint limit = std::sqrt(product);
        
        bigint result_a = -1, result_b = -1;

        for (bigint i = 1; i <= limit; ++i) {
            if (product % i == 0) {
                bigint j = product / i;
                if (gcd(i, j) == 1) {
                    result_a = i * G;
                    result_b = j * G;
                    // 找到第一個解就跳出
                    break; 
                }
            }
        }
        
        // 確保找到解
        if (result_a != -1) {
            std::cout << result_a << " " << result_b << std::endl;
        } else {
             // 其實這裡永遠不會執行,因為 i=1 總是一個因數,且 gcd(1, product)=1
             std::cout << -1 << std::endl;
        }
    }
    return 0;
}