avas55p1.cpp

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

const int maxn = 1e6 + 10;

bool composto[maxn];
int n;
vector<int> p[maxn];


void sieve()
{
	memset(composto, 0, sizeof(composto));

	composto[1] = true; // 1 nao eh primo

	for(int i = 2; i < maxn; i++)
	{
		if(!composto[i]) // se i eh primo
		{
			p[i].push_back(i); // i divide i
			for(int j = i + i; j < maxn; j+= i) // percorro os multiplos de i
			{
				composto[j] = true; // um multiplo de 1 nao eh primo
				p[j].push_back(i);// i divide um multiplo de i
			}
		}
	}
}

int func(int val, int i, int s = 1) // funcao recursiva para calcular a inclusao-exclusao
{
	// nesse caso "val" eh o valor do produto dos primos, "i" eh o indice do primo no vector p
	// e "s" eh o sinal da inclusao-exclusao
	int sum = 0;

	if(i == p[n].size()) return sum; // se ja visitei todos os primos que dividem N

	sum += s*(n/(val*p[n][i])) + func(val*p[n][i], i + 1, s*-1); //nesse caso eu uso o i-esimo primo
	// e calculo quantos numeros (val * p[n][i]) divide fazendo sempre a inclusao exclusao

	sum += func(val, i + 1, s); // caso eu nao use o i-esimo primo

	return sum;
}

int main()
{
	sieve();
	int t;

	cin >> t;

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

		cout << func(1, 0, 1) << "\n";
	}
}