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:
This file contains hidden or 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; | |
| } |
Comente