Cod sursa(job #2449907)

Utilizator mirceatlxhaha haha mirceatlx Data 21 august 2019 01:46:37
Problema GFact Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.25 kb
#include<cstdio>
#include<algorithm>
#define MAXD 510
using namespace std;
long long p,q;
long long divider[MAXD],power[MAXD],dividers=0;
void Decompose(long long x){
    int i;
    for(i=2;i*i<=x;i++)
        if(x%i==0){
            dividers++;
            divider[dividers]=i;
            while(x%i==0){
                x/=i;
                power[dividers]++;
            }
        }
    if(x!=1){
        dividers++;
        divider[dividers]=x;
        power[dividers]=1;
    }
}
bool Check(long long x){
    int i;
    long long value,y;
    for(i=1;i<=dividers;i++){
        value=0;
        y=divider[i];
        while(y<=x){
            value+=x/y;
            y*=divider[i];
        }
        if(value<power[i])
            return false;
    }
    return true;
}
int main(){
    freopen("gfact.in","r",stdin);
    freopen("gfact.out","w",stdout);
    int i;
    long long left,right,middle,answer;
    scanf("%lld%lld",&p,&q);
    Decompose(p);
    for(i=1;i<=dividers;i++)
        power[i]*=q;
    left=0;
    right=6e13;
    while(left<=right){
        middle=(left+right)/2;
        if(Check(middle)==true){
            answer=middle;
            right=middle-1;
        }
        else
            left=middle+1;
    }
    printf("%lld",answer);
    return 0;
}