TEMA
Wrong Answer 10%
ejbauer preguntado 6 years ago
Meu código está dando WA 10% e não encontro o erro. Alguém me ajuda!!
include <bits/stdc++.h>
using namespace std;
define T 1000100
bool primo[T];
void primos(int x){ int raiz = sqrt(x); for (int i = 4; i <= x; i+=2) primo[i] = 1;
for (int i = 3; i <= raiz; i+=2)
if (primo[i] == 0)
for (int j = i*i; j <= x; j+=i)
primo[j] = 1;
}
bool despojado(long long x){ int cont = 0; int raiz = sqrt(x); if (x % 2 == 0) {x /= 2; cont++;} if (x % 2 == 0) return false;
for (int i = 3; i <= raiz && x > 1; i += 2){
if (primo[i] == 0){
if (x%i == 0) {
x /= i; cont++;
if (x%i == 0) return false;
}
}
}
if (cont == 0 || (cont == 1 && x == 1)) return false;
return true;
}
int main(){
long long n;
cin >> n;
int raiz = sqrt(n);
primos(raiz);
int cont = 0;
for (int i = 1; i <= raiz; i++){
if (n%i == 0){
if (despojado(i)) cont++;
if (despojado(n/i)) cont++;
}
}
cout << cont << endl;
}