Problema
A função totiente de Euler, φ(n), conta os inteiros k com 1 ≤ k ≤ n e mdc(k, n) = 1. Por exemplo, φ(9) = 6, porque 1, 2, 4, 5, 7 e 8 não têm fator comum com 9.
Implemente eulers_totient(n).
Contar um k de cada vez é lento demais para n até 10^12. Use a fórmula do produto: φ(n) = n × (1 − 1/p) para cada primo distinto p que divide n. Fazendo a conta com inteiros, como n / p × (p − 1), você evita frações.
Entrada
n: um inteiro positivo.
Saída
Retorne φ(n). Pela definição, φ(1) = 1.
Restrições
1 ≤ n ≤ 10^12
Exemplos
Entrada:
n = 36
Saída esperada:
expected = 12
Entrada:
long long n = 36;
Saída esperada:
long long expected = 12;
Entrada:
long n = 36;
Saída esperada:
long expected = 12;
Explicação
36 = 2² × 3², então φ(36) = 36 × (1 − 1/2) × (1 − 1/3) = 36 × 1/2 × 2/3 = 12.
Entrada:
n = 13
Saída esperada:
expected = 12
Entrada:
long long n = 13;
Saída esperada:
long long expected = 12;
Entrada:
long n = 13;
Saída esperada:
long expected = 12;
Explicação
13 é primo, então todo k de 1 a 12 é primo com ele e φ(13) = 12.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Fatore n por divisões sucessivas até √n.
Dica 2
Para cada primo distinto p, troque o resultado por resultado / p × (p − 1); divida primeiro para que o valor continue pequeno.
Dica 3
Um fator que sobra acima de 1 depois do laço também é primo.
Complexidade esperada
tempo O(√n), espaço extra O(1)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.