URI PROBLEMA 1233 - Estrela SOLUÇÃO EM C++

URI Online Judge | 1233

Estrela

Maratona de Programação da SBC  Brasil

Timelimit: 2

Fernando ganhou um compasso de aniversário, e agora sua diversão favorita é desenhar estrelas: primeiro, ele marca N pontos sobre a circunferência, dividindo-a em N arcos iguais; depois, ele liga cada ponto ao k-ésimoponto seguinte, até voltar ao ponto inicial.

Dependendo do valor de k, Fernando pode ou não atingir todos os pontos marcados sobre a circunferência; quando isto acontece, a estrela é chamada de completa. Por exemplo, quando N = 8, as possíveis estrelas são as mostradas no desenho abaixo; as estrelas (a) e (c) são completas, enquanto as estrelas (b) e (d) não o são.

Dependendo do valor de N, pode ser possível desenhar muitas estrelas diferentes; Fernando pediu que você escrevesse um programa que, dado N, determina o número de estrelas completas que ele pode desenhar.

Entrada

Cada caso de teste contém de uma única linha, contendo um único inteiro N (3 ≤ N < 231), indicando o número de arcos no qual a circunferência foi dividida.

Saída

Para cada caso de teste, seu programa deve imprimir uma única linha contendo um único inteiro, indicando o número de estrelas completas que podem ser desenhadas.

#include <cstdio>

typedef long long ll;

ll phi(ll n){

double result = n;

for(ll i=2;i*i<=n;i++){

if(n % i == 0){

while(n % i == 0) n /= i;

result *= (1.0 - (1.0/(double)i));

}

}

if(n != 1) result *= (1.0 - (1.0/(double)n));

return (ll)result;

}

int main(){

ll n;

while(scanf("%lld",&n) != EOF){

printf("%lld\n",phi(n)/2);

}

return 0;

}