Cod sursa(job #359330)

Utilizator Abi79Iordache Albert Abi79 Data 26 octombrie 2009 17:42:14
Problema GFact Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <stdio.h>

FILE *f,*s;

long p,q,l,i,j,x,y,cat,rez;

struct putere
{
	long x; //x la puterea y
	long y;
};	
	
putere v[2000];

void cautBin()
{
	int st=1;
	int dr=2000000;
	
	long mj;
	
	cat=0;
	
	while(st<=dr)
	{
		mj=(st+dr)/2;
		
		//cat=0;
		
		y=v[i].x; //puterea, nu la cat
		while(y<=mj)
		{
			cat+=mj/y;
			y*=v[i].x;
		}	
		
		if(cat==v[i].y)
			break;
			
		if(cat<v[i].y)
			st=mj+1;
		
		if(cat>v[i].y)
			dr=mj-1;
	}

	if(mj>rez)
		rez=mj;
	
}	

int main()
{
	f=fopen("gfact.in","r");
	s=fopen("gfact.out","w");
	
	fscanf(f,"%ld %ld",&p,&q);
	
	x=0;
	while(p%2==0)
	{
		x++;
		p/=2;
	}	
	
	if(x>0)
	{
		l++;
		
		v[l].x=2;
		v[l].y=x;
	}	
	
	for(i=3;i*i<=p;i+=2)
	{
		x=0;
		while(p%i==0)
		{
			x++;
			p/=i;
		}	
	
		if(x>0)
		{
			l++;
		
			v[l].x=i; //puterea
			v[l].y=x; //la ce putere
		}
	}	
	
	if(p>1)
	{
		l++;
		
		v[l].x=p; //p
		v[l].y=1; //la 1
	}	
	
	for(i=1;i<=l;i++)
		v[i].y*=q;
		
	for(i=1;i<=l;i++)
		cautBin();
	
	fprintf(s,"%ld",rez);
	
	fclose(s);
	
	return 0;
}