Some hints (actually, I didn't solve problem but I'm sure this things will help for solving):

Lemma. Let d be divisor of n and GCD(n, x) = d (here x is some number). Then x = d * k for some positive integer k. Then .

Theorem. Let . Then . Here φ(n) is Euler function.

Bonus :) You can calculate φ(i) in O(nlogn) with Euler sieve.

void euler() {
    for (int i = 2; i < MAX; i++) phi[i] = i;
    for (int i = 2; i < MAX; i += 2) phi[i] /= 2;
    for (int i = 3; i < MAX; i += 2)
        if (phi[i] == i)
            for (int j = i; j < MAX; j += i) phi[j] -= phi[j] / i;
}

here is how I solved it :

let x = gcd(d,) ... this means the x|d and x| which means that x²|k that means that you can compute the answer as the contribution of every x where x^2 <= 10^15

for any x with x² ≤ 10¹⁵ notice that for any k with x²|k ... let d be any divisor such that x|d and x| then x will be counted times where σ₀(n) is the number of divisor of n ,but there is a catch .. what if there is a y = q * x with y²|k

the way around it is to subtract y's contribution leading to a formula :

but now you ask how to compute ,well there is a way to compute in O() actually it works for any power of the divisors in the same time which is O(* (time to compute )) ,I explained it briefly on the case of σ₁ here ,the famous mathematician Terence Tao explained it here and you can test your understanding of it on this problem

so the answer is where and N = 10¹⁵

the time to compute all σ₀ is

the time to compute the contribution after previous step is then the total time is