제출 #1334059

#제출 시각아이디문제언어결과실행 시간메모리
1334059kokokaiEuklid (COCI20_euklid)C++20
110 / 110
1 ms344 KiB
#include <iostream>
#include <numeric>

using namespace std;

void solve() {
    long long g, h;
    cin >> g >> h;

    // Trường hợp 1: g là ước của h
    if (h % g == 0) {
        if (g == h) {
            cout << h << " " << h << "\n";
        } else {
            cout << h + g << " " << h << "\n";
        }
        return;
    }

    // Trường hợp 2: Tổng quát
    // Tìm B nhỏ nhất sao cho B * g có chữ số đầu tiên là 1 trong cơ số h
    long long B = 1;
    while (true) {
        unsigned long long V = (unsigned long long)B * g;
        unsigned long long P = 1; // P lưu lũy thừa lớn nhất của h mà <= V
        
        while (P <= V / h) {
            P *= h;
        }
        
        // Kiểm tra điều kiện chữ số đầu tiên là 1
        if (V < 2 * P) {
            break;
        }
        B++;
    }

    // Tìm A sao cho floor(A/B) = h và gcd(A, B) = 1
    long long A = h * B;
    while (std::gcd(A, B) != 1) {
        A++;
    }

    cout << A * g << " " << B * g << "\n";
}

int main() {
    // Tối ưu I/O cho CP
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...