Playing with GCD

Explicación

La cota $N$ dada en cada caso solo acota el valor más grande del par. Así, si podemos precomputar de forma eficiente la cantidad de $x < n$ válidos para cada valor más grande $n$, podemos responder las consultas de forma eficiente. Las consultas se pueden responder en $\mathcal{O}(1)$ haciendo sumas de prefijos de $f(n)$, donde $f(n) = n - \phi(n)$. Tomamos el complemento de $\phi(n)$ porque $\phi(n)$ cuenta el número de valores $x \le n$ con $\gcd(x, n)=1$, pero queremos los valores de $x$ donde $\gcd(x,n) > 1$, que son el resto de los valores.

Implementación

Complejidad temporal: $\mathcal{O}(N\log\log N + N)$

#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 1e5;
 
int phi[MAXN + 1];
 
void precompute() {
	for (int i = 1; i <= MAXN; i++) { phi[i] = i; }
 
	for (int i = 2; i <= MAXN; i++) {
		// Si i es primo
		if (phi[i] == i) {
			for (int j = i; j <= MAXN; j += i) { phi[j] -= phi[j] / i; }
		}
	}
 
	for (int i = 1; i <= MAXN; i++) {
		// Sumamos los pares con gcd > 1, que es i - phi[i]
		phi[i] = phi[i - 1] + (i - phi[i]);
	}
}
 
int main() {
	int t;
	cin >> t;
 
	precompute();
 
	for (int i = 1; i <= t; i++) {
		int n;
		cin >> n;
		cout << "Case " << i << ": " << phi[n] << '\n';
	}
}