Sau 1 bước, bông tuyết sẽ có thêm ~x~ nút mới, sau 2 bước, bông tuyết sẽ có thêm ~x^2~ nút mới,...sau ~i~ bước, bông tuyết sẽ có thêm ~x^i~ nút mới. Vì thế, với mỗi ~n~, bài toán trở thành tìm cặp nghiệm (~x, i~) của phương trình ~1+x+x^2+x^3+...+x^i = n~.

Ta sẽ chia bài toán thành 2 trường hợp:

~x \le 10^6~:

• Với trường hợp này, ta sẽ tính trước đáp án với mọi cặp (~x, i~). Nhận thấy rằng ~i \le 60~ (vì ~2^{60} > 10^{18}~), vì thế với mỗi ~x~ trong khoảng [~2, 10^6~], ta chỉ duyệt ~i~ tối đa 60 lần, cuối cùng ta dùng map để lưu đáp án. Độ phức tạp cho trường hợp này có thể rất lớn, tuy nhiên nếu cài đặt đủ khéo thì với giới hạn này của bài toán vẫn đủ để cho ta vượt qua.

~x > 10^6~:

• Với trường hợp ~x > 10^6~, nhận thấy rằng ~i~ chỉ có thể là 2 (vì ~x^3 > 10^{18}~), vì thế bài toán trở thành tìm nghiệm của phương trình ~1+x+x^2=n~ hay ~x^2+x-n+1=0~, ta có thể dùng công thức giải phương trình bậc hai để tìm nghiệm của phương trình trên.

#include <bits/stdc++.h>

using namespace std;

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

    unordered_map<long long, pair<int, int>> f;
    for (int i = 2; i <= 1e6; i++)
    {
        long long sum = 1+i, cur = i, d = 2;
        while (sum <= 1e18)
        {
            if (cur > 1e18/i) break;
            cur *= i;
            sum += cur;
            if (sum > 1e18) break;
            if (f.find(sum) == f.end()) f[sum] = {i, d};
            d++;
        }
    }

    int t;
    cin >> t;
    while (t--)
    {
        long long n;
        cin >> n;
        pair<long long, int> ans = {LLONG_MAX, 0};
        if (f.find(n) != f.end()) ans = f[n];
        long long delta = 1 + 4*n - 4;
        if (delta >= 0)
        {
            long double x = (sqrtl(delta)-1)/2.0;
            if (abs(x-round(x)) < 1e-9 && x > 1) ans = min(ans, {x, 2});
        }
        if (ans.first == LLONG_MAX) cout << -1;
        else cout << ans.first << ' ' << ans.second;
        cout << '\n';
    }

    return 0;
}