Cod sursa(job #801205)

Utilizator Master011Dragos Martac Master011 Data 23 octombrie 2012 18:44:23
Problema GFact Scor 35
Compilator c Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <stdio.h>

int factori[32],puteri[32],n;
long long  p,q,rez;

void desc(long long p)
{
    long long i;
    for(i=2 ; i*i<=p ; i++)
        if(n%i==0)
        {
            factori[n] = i;
            while(p%i == 0)
            {
                p /= i;
                puteri[n]++;
            }
            n++;
        }
    if(p!=1)
    {
        factori[n] = p;
        puteri[n++] = 1;
    }
}

long long putere(long long x, long long p)
{
    long long nr = 0;
    while(x>=p)
    {
        nr += x/p;
        x /= p;
    }
    return nr;
}

long long zero(long long x){//returneaza 1 daca n! se imparte la p^q
    int i;
    for(i=0 ; i<n ; i++)
        if(putere(x,factori[i])<puteri[i]*q) return 0;
    return 1;
}
long long caut(long long p, long long q){
    long long n=0,pas=(long long)1<<62;
    while(pas>0){
        if(zero(n+pas)==0)
            n+=pas;
        pas/=2;
    }
   return n+1;
}

int main(){
    FILE *fin,*fout;
    fin=fopen("gfact.in","r");
    fout=fopen("gfact.out","w");
    fscanf(fin,"%lld%lld",&p,&q);
    //fscanf(fin,"%I64d%I64d",&p,&q);
    desc(p);
    rez=caut(p,q);
    fprintf(fout,"%lld",rez);
    //fprintf(fout,"%I64d",rez);
    fclose(fin);
    fclose(fout);
    return 0;
}