Cod sursa(job #2528903)

Utilizator Stefan_PiscuPiscu Stefan Constantin Stefan_Piscu Data 22 ianuarie 2020 19:03:59
Problema GFact Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("gfact.in");
ofstream fout("gfact.out");

struct prime{
    long long val;
    long long e;
};

vector<prime> v;
long long p, q;

vector<prime> getprimes(long long x){
    vector<prime> v;
    if(x%2==0) v.push_back({2, 0});
    while(x%2==0) x/=2, v[v.size()-1].e++;
    long long d=3;
    while(d*d<=x){
        if(x%d==0) v.push_back({d, 0});
        while(x%d==0) v[v.size()-1].e++, x/=d;
        d+=2;
    }
    if(x>1) v.push_back({x, 1});
    return v;
}

void init(){
    fin>>p>>q;
    v=getprimes(p);
}

long long getpow(long long x, long long n){
    long long sol=0;
    while(x<=n){
        sol+=n/x;
        n/=x;
    }
    return sol;
}

bool can(long long mid){
    for(auto i:v){
        if(getpow(i.val, mid)<i.e*q){
            return 0;
        }
    }
    return 1;
}

long long binsrc(){
    long long st=1, dr=p*q, sol=dr;
    while(st<=dr){
        long long mid=(st+dr)/2;
        if(can(mid)){
            dr=mid-1;
            sol=mid;
        }
        else{
            st=mid+1;
        }
    }
    return sol;
}

int main(){
    init();
    fout<<binsrc()<<"\n";
    return 0;
}