Cod sursa(job #475141)
#include <fstream>
using namespace std;
const int MAX = 1 << 28;
void Read();
void Solve();
bool Test(int x);
void Write();
int p, q, lf;
int res;
int main()
{
Read();
Solve();
Write();
}
void Read()
{
ifstream fin("gfact.in");
fin >> p >> q;
fin.close();
}
void Solve()
{
int cl = p;
for (int i = 2; i * i <= p; ++i)
{
if (cl % i == 0)
{
lf = i;
while (cl % i == 0)
cl /= i;
}
if (i != 2) ++i;
}
if (cl != 1)
lf = cl;
int step;
for (step = 1; (step << 1) <= MAX; step <<= 1);
for (res = MAX + 1; step; step >>= 1)
if (res - step >= 1 && Test(res - step))
res -= step;
}
bool Test(int x)
{
int now = lf, ex = 0;
while (now <= x)
{
ex += x / now;
now *= lf;
}
return (ex >= q);
}
void Write()
{
ofstream fout("gfact.out");
fout << res;
fout.close();
}