Solução Informática Avançado - Semana 55 - Problema 1

Note que se $gcd(a, b) \neq 1$ então $a$ e $b$ possuem algum fator primo em comum. Usando o fato de que entre $1$ e $N$ um número $p$ divide exatamente $\frac{N}{p}$ (divisão inteira) números. Então, podemos calcular o conjunto $P$ de primos que dividem $N$ e depois somamos todas as divisões inteiras para cada primo de $P$ , porém, alguns primos podem acabar dividindo o mesmo número, ou seja, no final o nosso código vai contar o mesmo número duas vezes. Por exemplo:

Se $N = 10$ , então $P = {2, 5}$ . $2$ divide os números $2, 4, 6, 8, 10$ e $5$ divide os números $5, 10$ . Note que $\frac{10}{2} + \frac{10}{5} = 7$ quando na verdade a resposta é $6$ . Isso se dá por que o número $10$ foi contado duas vezes.

Então como resolver esse problema de que os números podem acabar sendo contados várias vezes? Simples, usando o princípio da inclusão-exclusão que diz, dados dois conjuntos $A$ e $B$ :

$A \cup B = A + B - A\cap B$

Então, para os dois conjuntos do exemplos, se $A$ for o conjunto dos múltiplos de $2$ menores ou iguais a $N$ e $B$ o de $5$ então

$A \cup B = A + B - A \cap B \ \implies A\cup B = \frac{10}{2} + \frac{10}{5} - \frac{10}{10} = 6$

Portanto, basta calcular todos os primos divisores de $N$ usando o algoritmo do crivo de Eratóstenes, já que $N \leq 10^6$ , e depois usar inclusão-exclusão nos primos que o dividem.

Código para melhor entendimento:

	#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/(valp[n][i])) + func(valp[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";
	}
	}

view raw

avas55p1.cpp

hosted with ❤ by GitHub