Subtask 1: https://ideone.com/YxS3TK

ĐPT: ~\mathcal{O}~(~T \times n^2 \times logn~).

Subtask 2:

Từ điều kiện của đề bài: ~\gcd(x, n) \times \gcd(y, n)=\gcd(x \times y, n)~.

Điều kiện tương đương với: ~\gcd(x, n) \times \gcd(y, n)~ là ước của ~n~

Gọi ~f(d)~ là số lượng số ~x~ mà ~1\le x \le n~, ~\gcd(x, n)=d~ với ~d~ là ước của ~n~.

Dễ thấy ~f(d)=\phi(n/d)~, với ~\phi~ là hàm Euler totient.

Các bạn có thể tìm hiểu thêm về hàm Euler totient tại đây.

Gọi ~a(i, j)~ là số cặp ~(x, y)~ mà:

• ~i \neq j~.
• ~i \times j~ là ước của ~n~.
• ~\gcd(x, n)=i~.
• ~\gcd(y, n)=j~.
• ~1 \le x, y \le n~.

Dễ thấy rằng ~a(i, j)=f(i) \times f(j)~.

Gọi ~b(i)~ là số cặp ~(x, y)~ mà:

• ~i^2~ là ước của ~n~.
• ~\gcd(x, n)=i~.
• ~\gcd(y, n)=i~.
• ~1 \le x, y \le n~.

Dễ thấy rằng ~b(i)= \frac{f(i) \times (f(i)+1)}{2}~.

Ở đây do ~x>y~ và ~x<y~ đối xứng nhau nên ta sẽ phải chia đôi.</p>

Vậy nên đáp án của bài này là: ~\frac{\sum_{i, j \in d(n)} a(i, j)}{2}+\sum_{i \in d(n)} b(i)~, với ~d(n)~ là tập các ước của ~n~.

Chú ý để có độ phức tạp này các bạn phải chuẩn bị trước mọi ước của ~i~ từ ~1~ đến ~n~ và tính phi trước.

Các bạn có thể đọc thêm về precalc phi tại đây.

ĐPT: ~\mathcal{O}~ ~(n \times logn + \sum_{i=1}^{10^5} d(i)^2) \approx 1166750~.

#include <bits/stdc++.h>
#define el '\n'
#define fi first
#define sc second
#define int ll
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
const int mod=1e9+7;
const int N=1e5+11;
const int lim=1e5;
int n, phi[N];
ll ans[N];
vector<int> uoc[N];
void sang()
{
    for(int i=1;i<=lim;i++) for(int j=i;j<=lim;j+=i) uoc[j].push_back(i);
}
void prepare()
{
    for(int i=1;i<=lim;i++) phi[i]=i;
    for(int i=2;i<=lim;i++)
    {
        if(phi[i]==i)
        {
            for(int j=i;j<=lim;j+=i)
            {
                phi[j]-=phi[j]/i;
            }
        }
    }
}
ll sol(int n)
{
    ll ans=0;
    for(auto x:uoc[n])
    {
        for(auto y:uoc[n])
        {
            ll tmp=x*y;
            if(tmp>n) break;
            if(x!=y && n%(tmp)==0)
            {
                ans+=phi[n/x]*phi[n/y];
            }
        }
    }
    ans/=2;
    for(auto x:uoc[n])
    {
        ll tmp=x*x;
        if(tmp>n) break;
        if(n%(tmp)==0) ans+=phi[n/x]*(phi[n/x]+1)/2;
    }
    return ans;
}
signed main()
{
//    freopen("divisor.INP", "r", stdin);
//    freopen("divisor.OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    sang();
    prepare();
    for(int i=1;i<=lim;i++) ans[i]=sol(i);
    int t=1;
    cin >> t;
    while(t--)
    {
        cin >> n;
        cout << ans[n] << el;
    }
}