Solução Estrela

0 Flares Facebook 0 0 Flares ×

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:

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: