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/(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