Tóm tắt đề bài: Cho số nguyên dương ~K~, cần tìm số nguyên dương ~N~ nhỏ nhất sao cho

với S(N) là tổng các chữ số của ~N~.

Ý tưởng chính: Khi cộng ~1~ vào ~N~, sẽ có ~2~ trường hợp xảy ra:

• Nếu ~N~ không kết thúc bằng chữ số ~9~ thì ~S(N + 1) = S(N) + 1~.

• Nếu ~N~ kết thúc bằng ~t~ chữ số ~9~ thì ~S(N + 1) = S(N) - 9t + 1~.

Trường hợp ~1~ chỉ xảy ra nếu ~K = 1~, khi đó ~N_{min} = 1~. Còn lại, phải tìm ~N_{min}~ sao cho:

• ~S(N) \equiv 0 \pmod{K}~

• ~S(N + 1) \equiv S(N) - 9t + 1 \equiv 0 \pmod{K}~

Suy ra: ~9t - 1 \equiv 0 \pmod{K}~ hay ~9t \equiv 1 \pmod{K}~.

Như vậy, bài toán trở thành tìm ~t~ nhỏ nhất sao cho ~9t \equiv 1 \pmod{K}~.

Trước hết, phương trình trên có nghiệm khi và chỉ khi ~\gcd(9, K) = 1~. Nếu điều kiện này không thỏa mãn thì không tồn tại ~N~, do đó in ra ~-1~.

Giả sử ~\gcd(9, K) = 1~, khi đó tồn tại nghịch đảo modulo của ~9~ theo modulo ~K~, ký hiệu là: ~t = 9^{-1} \bmod{K}~.

Giá trị ~t~ có thể được tìm bằng thuật toán Euclid mở rộng trong thời gian ~O(\log K)~.

Sau khi tìm được ~t~, ta biết rằng số ~N~ phải có đúng ~t~ chữ số ~9~ ở cuối. Khi đó:

với ~A~ là phần đứng trước.

Từ điều kiện: ~S(N) \equiv 0 \pmod{K} \Rightarrow S(A) + 1 \equiv 0 \pmod{K}~ suy ra: ~S(A) \equiv -1 \equiv K - 1 \pmod{K}~

Để ~N~ nhỏ nhất, ta chọn: ~S(A) = K - 1~

Bài toán tiếp theo là xây dựng số ~A~ nhỏ nhất có tổng chữ số bằng ~K - 1~. Để tối thiểu hóa giá trị số, ta sử dụng chiến lược tham lam:

• Sử dụng càng nhiều chữ số ~9~ càng tốt (để giảm số chữ số)

• Phần dư còn lại sẽ là chữ số đầu tiên

Độ phức tạp: ~O(T \log K)~

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ll long long

ll K;

namespace two {
    const int N = 1e5 + 5;
    bool mark[N];

    void solve() {
        fill(mark, mark + K, false);
        int x = 9;

        while (!mark[1]) {
            if (mark[x % K]) break;
            mark[x % K] = true;
            x += 9;
        }

        if (!mark[1]) return cout << -1 << '\n', void();
        x -= 9;

        int fir, height = x;

        if (K - 1 <= 8) {
            fir = K - 1;
            height += K - 1;
        } else {
            height += 8;
            int tmp = K - 1 - 8;

            if (tmp == 0) 
                fir = 8;
            else {
                height += 9 * (tmp / 9);
                tmp %= 9;

                if (tmp) height += tmp, fir = tmp;
                else fir = 9;
            }
        }

        cout << fir << ' ' << height << '\n';
    }
}

namespace all {
    ll extEuclid(ll a, ll b, ll &x, ll &y) {
        if (b == 0) {
            x = 1;
            y = 0;
            return a;
        }
        ll x1, y1;
        ll d = extEuclid(b, a % b, x1, y1);
        x = y1;
        y = x1 - y1 * (a / b);
        return d;
    }

    int modInv(int a, int m){
        int x, y;
        ll d = extEuclid(a, m, x, y); 
        if (d != 1) return -1; 
        x = (x % m + m) % m;
        return x; 
    }

    void solve() {
        if (__gcd(9LL, K) != 1) return cout << -1 << '\n', void();
        ll inv = modInv(9, K);
        ll x = 9LL * inv;

        int fir, height = x;

        if (K - 1 <= 8) {
            fir = K - 1;
            height += K - 1;
        } else {
            height += 8;
            int tmp = K - 1 - 8;

            if (tmp == 0)
                fir = 8;
            else {
                height += 9LL * (tmp / 9);
                tmp %= 9;

                if (tmp) height += tmp, fir = tmp;
                else fir = 9;
            }
        }

        cout << fir << ' ' << height << '\n';
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    // #ifndef ONLINE_JUDGE
    freopen("SODEP.inp", "r", stdin);
    freopen("SODEP.out", "w", stdout);
    // #endif

    int Q; cin >> Q;
    while (Q--) {
        cin >> K;
        if (K == 1) {
            cout << 1 << ' ' << 1 << '\n';
            continue;  
        }
        // if (K <= 100000) {
        //  two::solve();
        //  continue;
        // }
        all::solve();
    }

    return 0;
}