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:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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"; | |
| } | |
| } |
Comente