Cod sursa(job #2788016)

Utilizator Andrei_TudorAndrei Tudor Andrei_Tudor Data 24 octombrie 2021 17:36:25
Problema GFact Scor 25
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <fstream>
using namespace std;
ifstream cin("gfact.in");
ofstream cout("gfact.out");

long long nrfact(long long f, long long d){
    long long p = d;
    long long 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(){
    long long 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){
        long long d = 2;
        while(d * d <= p && p > 1){
            long long e = 0;
            while(p % d == 0){
                p /= d;
                e ++;
            }
            if(e > 0){
                long long 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;
}