Cod sursa(job #353476)

Utilizator Teodor94Teodor Plop Teodor94 Data 5 octombrie 2009 12:32:30
Problema GFact Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <cstdio>

long long p,q,f[1000],c[1000],nr;

void desc(long long y)  // descompunere in fact primi
{
	nr=0;
    for (int i=2;i*i<=y;i++)
        if (y%i==0)
        {
			nr++;
			f[nr]=i;
            c[i]=0;
            while (y%i==0)
            {
                y=y/i;
                c[i]++;
            }
        }
    if (y!=1) 
	{
		nr++;
		f[nr]=y;
		c[nr]=1;
	}
}

bool nrz(int n,int a,long long b)
{
	long long b2=0;
	while (n) 
		b2+=(n/=a);
	return b2>=b;
}

bool div(long long n)
{
	long long i;
	for (i=1;i<=nr;i++)
		if (!nrz(n,f[i],c[i]))
			return 0;
	return 1;
}

long long cautbin()
{
	long long i,pas=1<<30;
	for (i=0;pas;pas>>=1) // pas=pas/2;
		if (!div(i+pas))
			i=i+pas;
	return i+1;
}

int main()
{
	int i;
	freopen("gfact.in","r",stdin);
	freopen("gfact.out","w",stdout);
	scanf("%lld%lld",&p,&q);
	desc(p);
	for (i=1;i<=nr;i++) c[i]=c[i]*q;
	long long x=cautbin();
	printf("%lld",x);
	return 0;
}