~\large lcm(x, y) = gcd(x, y)^2~

~\iff~ ~\Large\frac{x \cdot y}{\mathcal{gcd(x, y)}} = gcd(x, y)^2~

~\iff~ ~\Large\frac{x}{gcd(x, y)} \cdot \frac{y}{gcd(x, y)} = n~

Vì ~\large gcd(\frac{x}{gcd(x, y)} \cdot \frac{y}{gcd(x, y)}) = 1~ nên ta cần tính tìm các cặp ~(a, b)~ sao cho ~a \cdot b = n~ và ~gcd(a, b) = 1~ sau đó nhân với ~n~

Vậy thì ta chỉ cần duyệt qua các ước ~i~ của ~n~ sao cho ~\large gcd(i, \frac{n}{i}) = 1~ và nhân tổng với ~n~. Độ phức tạp là ~\mathcal{O}(\sqrt{n} \cdot \mathcal{log}(n))~. Ta còn có thể cải tiến để bỏ qua phần kiểm tra ~\large gcd(i, \frac{n}{i})~, phần này xin nhường lại cho bạn đọc.

Code mẫu

#include <bits/stdc++.h>

using namespace std;

#define int int64_t
#define sz(x) (int)x.size()
#define MASK(i) ((1) << (i))
#define all(x) x.begin(), x.end()
#define BIT(x, i) ((x) >> (i) & 1)
#define DB(X) { cerr << #X << " = " << (X) << '\n'; }

template<class A, class B> bool maximize(A &a, B b) { return a < b && (a = b, true); }
template<class A, class B> bool minimize(A &a, B b) { return a > b && (a = b, true); }

const int MAXN = 1e5 + 6;
const int MOD = 1e9 + 7;

int t, n;

int pw(int x, int n) {
    int res = 1;
    while (n) {
        if (n & 1) res = res * x % MOD;
        n /= 2;
        x = x * x % MOD;
    }
    return res;
}

#define TASK ""
int32_t main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    #ifdef ONLINE_JUDGE
    //  freopen(TASK".inp","r",stdin);
    //  freopen(TASK".out","w",stdout);
    #endif

    cin >> t;

    while (t--) {
        cin >> n;

        vector<int> p;

        int m = n, x;
        for (int i = 2; i * i <= m; i++) {
            if ((m % i) > 0) continue;
            x = 1;
            while ((m % i) == 0) {
                x = x * i % MOD;
                m /= i;
            }
            p.push_back(x);
        }
        if (m > 1) p.push_back(m % MOD);

        int res = 0, k = sz(p), lim = MASK(k), A, B;
        for (int mask = 0; mask < lim; mask++) {
            A = 1, B = 1;
            for (int i = 0; i < k; i++) {
                if (BIT(mask, i)) {
                    A = A * p[i] % MOD;
                    B = (B * p[i] % MOD * p[i]) % MOD;
                }
                else {
                    B = B * p[i] % MOD;
                    A = (A * p[i] % MOD * p[i]) % MOD;
                }
            }

            res = (res + A + B) % MOD;
        }

        cout << res * pw(2, MOD - 2) % MOD << '\n';
    }

    return 0;
}
//196