Задача №114707. Деление
Из предметов в школе Олегу больше всего нравятся история и математика, а его любимый раздел математики — деление. Чтобы улучшить свои навыки в делении, Олег загадал два целых числа \(p\) и \(q\) и решил найти максимальное число \(x\), такое что \(p\) делится нацело на \(x\), а \(x\) не делится нацело на \(q\). Так как Олег очень хорош в делении, то он быстро нашёл нужное число. Теперь ему интересно, сможете ли вы тоже справиться с этой задачей.
В первой строке задано целое число \(p\) (\(1 \le p \le 10^{100}\)).
Во второй строке задано целое число \(q\) (\(2 \le q \le 10^{12}\)).
Можно показать, что при данных ограничениях существует хотя бы одно подходящее \(x\).
Выведите максимальное число \(x\), такое что \(p\) делится нацело на \(x\), а \(x\) не делится на \(q\).
В первом примере число \(x = 10\) подходит, так как это максимальный делитель \(10\), и \(10\) не делится на \(4\).
Во втором примере заметим, что число \(12\) не подходит в качестве \(x\), так как \(12\) делится на \(6\), \(6\) не подходит в качестве \(x\), так как \(6\) делится на \(6\), а следующий по величине делитель \(12\) — это \(4\), и \(x=4\) нам подходит, так как \(4\) не делится нацело на \(6\).
10 4
10
12 6
4
179 822
179