Solução Estrela

Solução por Lucca Siaudzionis

Após pensar um pouco, pode-se concluir que, para $$N$$ pontos, a resposta será $$\displaystyle \frac{\phi(N)}{2}$$, onde $$\displaystyle \phi$$ é a Função Totiente de Euler. Para se calcular $$\displaystyle \phi(N)$$, vamos usar duas propriedades:

• $$\displaystyle \phi(p^k) = (p-1)p^{k-1}$$, para $$p$$ primo.
• Se $$mdc(a, b) = 1 \Rightarrow \phi(ab) = \phi(a)\phi(b)$$.

Assim, se tivermos que um certo $$p$$ primo divide $$N$$ e a maior potência de $$p$$ que divide $$N$$ é $$p^k$$, podemos ir, usando essas duas propriedades, decompondo $$N$$ em vários valores que podem ser calculados facilmente.

O código, então, fica:

https://gist.github.com/luccasiau/2f9ccb9a5f5d6265e7e4