#include <cstdio>
#define FIN "gfact.in"
#define FOUT "gfact.out"
#define Q 30000
int p,q,b,v[Q][2];
void read()
{
	freopen(FIN, "r",stdin);
	scanf("%d%d", &p, &q);
}
int calc(int x,int y)
{
	int i=0;
	v[0][0]=1;
	v[0][1]=0;
	while (v[i][1]<=y)
	{
		++i;
		v[i][0]=v[i-1][0]*x;
		v[i][1]=x*v[i-1][1]+1;
	}
	return i;
}
void solve(int x,int y)
{
	int i,r=y;
	i=calc(x,y);
	while (r)
	{
		while (v[i][1]>r)
			--i;
		b+=(r/v[i][1])*v[i][0];
		r%=v[i][1];
	}
}
void comp()
{
	int i=1,j;
	while (p>1)
	{
		++i;j=0;
		if (p%i==0)
		{
			while (p%i==0)
			{
				++j;
				p/=i;
			}
			solve(i,j*q);
		}
	}
}
void write()
{
	freopen(FOUT,"w",stdout);
	printf("%d", b);
}
int main()
{
	read();
	comp();
	write();
}