Общие делители и целые квадраты

[Andrey A]

Простая вроде бы задача: даны два целых числа отличных от нуля $m$ и $M$. Требуется найти наибольшее $x$ такое, что $x\mid m$ и $x^2\mid M$.
Никак не пойму, можно ли тут обойтись без перебора делителей? Подумал сначала что $x=\dfrac{\gcd(m^2,M)}{\gcd(m,M)}$, но это не верно.

[12d3]

Andrey A в сообщении #1108797 писал(а):

Никак не пойму, можно ли тут обойтись без перебора делителей?

Вроде нельзя. Рассмотрим частный случай, когда $M | m$. Тогда от значения $m$ ответ не зависит, и требуется найти наибольший квадрат, делящий $M$, но без факторизации этого сделать нельзя. По крайней мере, не существует полиномиального алгоритма, который решал бы эту задачу.

[Andrey A]

Положим $y$ - основание наибольшего целого квадрата, делящего $M$. Тогда и в общем случае $x=\gcd(m,y)$. Если без $y$ не обойтись, то факторизация действительно необходима.

12d3 в сообщении #1108805 писал(а):

Вроде ...

Вот и мне померещилось.