Lời giải được cung cấp bởi bạn lftroq

Subtask 1:

Ta chỉ cần thử từng cặp ~(x, y)~ và kiểm tra xem có thỏa đề bài hay không.

Subtask 2:

Đặt:

• ~d = gcd(x, y)~

• ~x = u \cdot d~

• ~y = v \cdot d~

Tất nhiên ~gcd(u, v) = 1~.

Ta có: $$x + y + gcd(x, y) = a$$ $$\Leftrightarrow d \cdot (u + v + 1) = a$$ $$\Leftrightarrow u + v = \frac{a}{d} - 1$$

Như vậy ta chỉ cần chuẩn bị sẵn mảng ~cnt~ với ~cnt[k]~ là số cặp ~(u, v)~ thỏa:

• ~gcd(u, v) = 1~

• ~u + v = \frac{a}{d} - 1 = k~

Ta sẽ dùng nguyên lí bù trừ để giải quyết bài toán trên.

Giả sử ~k~ có ~t~ ước nguyên tố.

Gọi ~e_i~ là số nguyên tố thứ ~i~ (~1 \leq i \leq t~) mà ~k~ chia hết. ~S_i~ là biến cố ~gcd(u, x)~ chia hết cho ~e_i~. Tức ~|S_i|~ là số cặp ~(u, v)~ sao cho:

• ~gcd(u, v)~ ~\small{\vdots}~ ~e_i~

• ~u + v = k~

Vậy đáp án là:

$$|U| - \sum_{i = 1}^{t}|S_i| + \sum_{1 \leq i < j \leq t}|S_i \cap S_j| - ...$$

Ta có thể tính:

• ~|U| = k - 1~

• ~|\bigcap\limits_{1 \leq i \leq t} S_i| = \frac{k}{\prod_{i = 1}^{t} e_i} - 1~

Thuật toán này có thể dùng Harmonic series nên có thể chạy trong độ phức tạp ~O(a\log(a))~.

Như vậy ứng với mỗi ~d~ là ước của ~a~ (có thể tìm trong ~O(\sqrt{a})~) ta chỉ cần tổng cặp số thỏa điều kiện là ra được đáp án cuối cùng.

Subtask 3:

Cũng chuẩn bị sẵn mảng ~cnt~ như subtask 2. Tuy nhiên nếu như tìm các ước của ~a_i~ trong ~O(\sqrt{a})~ ta sẽ bị TLE vì thế ta có thể cải thiện phương pháp tìm ước của ~a_i~ trong thời gian tối ưu nhất.

Giả sử số nguyên dương ~m~ có tập ước là ~div[m]~.

Khi ta xét số nguyên dương ~p = e^c~ và ~m~ ~\not\vdots~ ~e~. Như vậy chỉ cần lấy một số trong ~div[m]~ nhân cho một số trong tập ~\{e^0, e^1, ..., e^c\}~ ta sẽ được một phần tử trong tập ~div[p]~.

Như vậy ta chỉ cần quy nạp với tập ban đầu ~div[1] = {1}~.

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

const int Nmax = 4e6 + 7;

int mu[Nmax];
int cnt[Nmax];
int lp[Nmax];
vector<int> pr;

void sieve() {
    for(int i=2;i<Nmax;i++) {
        if(!lp[i]) pr.push_back(lp[i]=i);
        for(int j=0;j<pr.size()&&pr[j]<=lp[i]&&i*pr[j]<Nmax;j++) {
            lp[i*pr[j]] = pr[j];
        }
    }
}

vector<int> factorize(int n) {
    vector<int> div{1};
    int tn = n;
    for(int p=lp[tn];tn!=1;p=lp[tn]) {
        int cnt = 0;
        while(tn % p == 0) tn/= p, cnt++;


        vector<int> nw;
        for(int j=p, i=1;i<=cnt;i++, j*= p) {
            for(int d : div) nw.push_back(d * j);
        }
        div.insert(div.end(), nw.begin(), nw.end());
    }
    return div;
}

void evadi(int Q, vector<int>& N) {
    sieve();
    mu[1] = 1;
    for (int i = 1; i <= Nmax; i++)
      for (int j = 2*i; j <= Nmax; j += i)
          mu[j] -= mu[i];

    for(int i=Nmax-1;i>0;i--) {
        cnt[i] = i-1;
        for(int j=i*2;j<Nmax;j+=i) {
            cnt[j]+= cnt[i] * mu[j/i];
        }
    }

    for(int i=0;i<Q;i++) {
        int n = N[i];
        vector<int> div = factorize(n);
        long long ans = 0;

        for(int d : div) {
            ans+= cnt[n / d - 1];
        }
        N[i] = ans;
    }
}

int main() {
    cin.exceptions(istream::failbit);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int Q;
    cin >> Q;
    vector<int> N(Q);
    for (int& i : N) {
        cin >> i;
    }

    evadi(Q, N);

    for (int i = 0; i < Q; i++) {
      cout << N[i] << " ";
    }
    cout << endl;

    return 0;
}