Solução por Lucca Siaudzionis
Após pensar um pouco, pode-se concluir que, para 
pontos, a resposta será 
, onde 
é a Função Totiente de Euler. Para se calcular 
, vamos usar duas propriedades:
, para 
primo.- Se
.
Assim, se tivermos que um certo primo divide e a maior potência de que divide é 
, podemos ir, usando essas duas propriedades, decompondo em vários valores que podem ser calculados facilmente.
O código, então, fica:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // | |
| // estrela.cpp | |
| // programas2 | |
| // | |
| // Created by Lucca Siaudzionis on 18/03/13. | |
| // Copyright (c) 2013 Luccasiau. All rights reserved. | |
| // | |
| #include <cstdio> | |
| #include <vector> | |
| #define MAXP 55050 | |
| using namespace std; | |
| int n; | |
| int marc[MAXP]; | |
| vector<int> primos; | |
| int isprime(int x){ | |
| if(x == 2) return 0; | |
| for(int i = 0;i<primos.size();i++){ | |
| if(primos[i]*primos[i] > x) break; | |
| if(x % primos[i] == 0) return primos[i]; | |
| } | |
| return 0; | |
| } | |
| int maxexp(int d,int x){ | |
| if(x % d) return 0; | |
| return 1+(maxexp(d,x/d)); | |
| } | |
| int phi_prime(int p,int exp){ | |
| int aux = 1; | |
| for(int i = 1;i<=exp-1;i++) aux *= p; | |
| return aux*(p-1); | |
| } | |
| int phi(int x){ | |
| if(x <= 1) return 1; | |
| int davez = isprime(x); | |
| if(!davez) return x-1; | |
| int exp = maxexp(davez,x); | |
| int aux=1; | |
| for(int i = 1;i<=exp;i++) aux *= davez; | |
| return phi_prime(davez,exp)*phi(x/aux); | |
| } | |
| int main(){ | |
| for(int i = 2;i<MAXP;i++){ // Crivo de Erastótenes | |
| if(!marc[i]){ | |
| primos.push_back(i); | |
| for(int j = i+i;j<MAXP;j+=i) marc[j] = 1; | |
| } | |
| } | |
| while( scanf("%d",&n) != EOF ){ | |
| printf("%d\n",phi(n)/2); | |
| } | |
| return 0; | |
| } |