Cod sursa(job #2788014)
Utilizator | Andrei Tudor Andrei_Tudor | Data | 24 octombrie 2021 17:24:41 |
---|---|---|---|
Problema | GFact | Scor | 20 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 1.38 kb |
#include <fstream>
using namespace std;
ifstream cin("gfact.in");
ofstream cout("gfact.out");
int nrfact(int f, int d){
int p = d;
int x = 0;
while(f / p > 0){
x = x + (f / p);
p *= d;
}
return x;
}
bool prime(int n){
if(n != 2 && n % 2 == 0) { return 0; }
else if(n == 0 || n == 1) { return 0; }
for(int i = 3; i * i <= n; i += 2){
if(n % i == 0){
return 0;
}
}
return 1;
}
int main(){
int p, q, sol;
cin >> p >> q;
if(prime(p) == 1){
sol = 0;
while(nrfact(sol, p) != q){
if(nrfact(sol, p) < q){
sol += p;
}
else {
sol --;
}
}
}
else if(prime(p) == 0){
int d = 2;
while(d * d <= p && p > 1){
int e = 0;
while(p % d == 0){
p /= d;
e ++;
}
if(e > 0){
int x = 0;
while(nrfact(x, d) != e * q){
if(nrfact(x, d) < e * q){
x += d;
}
else {
x --;
}
}
sol = max(sol, x);
}
d ++;
}
}
cout << sol;
return 0;
}