«Ввод GCD»: жертва переменной ради жёстких ограничений

В задачах с двумя (или несколькими) целочисленными переменными часто выгодно «вынести» их общий делитель: пусть $$$d=\gcd(x,y)$$$, тогда $$$x=a d,\ y=b d$$$ и $$$\gcd(a,b)=1$$$. Да, переменных стало на одну больше (появился $$$d$$$), но взамен вы получили сильное условие взаимной простоты для $$$a,b$$$. Это резко сужает перебор делителей, заставляет делимости «распадаться» на простые случаи и упрощает добивание перебором/оценками.

Как применять (шаблон из 6 шагов)

1. Нормализация. Уберите нули/знаки (если нужно, рассмотрите случаи $$$x=0\leftrightarrow y=0$$$, $$$x,y \gt 0$$$ и т.п.).
2. Ввод GCD. Положите $$$d=\gcd(x,y)$$$, $$$x=a d$$$, $$$y=b d$$$, где $$$\gcd(a,b)=1$$$.
3. Сократите $$$d$$$. Поделите исходное уравнение/делимость на максимальную степень $$$d$$$.
4. Разорвите делимости. Любая делимость вида $$$U(a,b)\mid V(a,b)$$$ на взаимно-простых часто ведёт к тому, что большой множитель обязан делить один «жёсткий» фактор.
5. Добейте короткими леммами про $$$\gcd$$$. Типовые факты (доказываются по Евклиду в 1–3 шага):

• $$$\gcd(a^2+b^2,\ ab)=1$$$ при $$$\gcd(a,b)=1$$$.
• $$$\gcd(a+b,\ a^2-ab+b^2)=1$$$ при $$$\gcd(a,b)=1$$$.
• Если $$$m$$$ нечётно, то $$$\gcd(a^m-b^m,\ ab)=1$$$ при $$$\gcd(a,b)=1$$$.

1. Финишируйте перебором малых вариантов / делителей. После шага 4 обычно остаётся конечный набор значений (часто — делители простого/почти простого числа), который легко перебрать.

Четыре показательных скетча

1) BMO 2017 P1

Найти все пары положительных целых $$$(x,y)$$$, такие что

Ход: $$$x=ad,\ y=bd,\ \gcd(a,b)=1$$$. Тогда

Отсюда $$$(a^2+42ab+b^2)\mid d(a+b)(a^2-ab+b^2)$$$, а по взаимной простоте легко получить

Но $$$\gcd(ab,\ a^2-ab+b^2)=1$$$ (см. леммы), значит $$$a^2-ab+b^2\mid 43$$$. Итого $$$a^2-ab+b^2\in{1,43}$$$ — дальше добивка коротким перебором (квадраты растут быстро).

2) JBMO SL 2019 N3

Найти все простые $$$p$$$ и целые неотрицательные $$$x\neq y$$$, такие что

Ход: $$$x=ad,\ y=bd,\ \gcd(a,b)=1$$$. Тогда

Проверкой лемм: $$$\gcd\big((a+b)(a^2+b^2),\ a^2-ab+b^2\big)=1$$$. Значит $$$p\mid(a+b)(a^2+b^2)$$$, что невозможно для простого $$$p$$$ при $$$a,b \gt 0$$$. Вывод: один из $$$x,y$$$ равен нулю $$$\Rightarrow (x,y)=(0,p),(p,0)$$$.

3) JBMO SL 2021 N5

Найти все целые решения $$$x^2+5y^2=2021y$$$. Ход: сначала замечаем: $$$x=0\iff y=0$$$. Далее $$$x \gt 0\Rightarrow y \gt 0$$$. Вводим $$$x=ad,\ y=bd,\ \gcd(a,b)=1$$$. Получаем

Из $$$\gcd(a^2+5b^2,\ b)=1$$$ следует $$$a^2+5b^2\mid 2021$$$ (простое разложение — дальше короткий перебор по делителям 2021).

4) JBMO 2018 P1

Найти все целые $$$m,n$$$, для которых $$$m^5-n^5=16mn$$$. Ход: $$$m=0\iff n=0$$$. При $$$mn\neq0$$$: $$$m=ad,\ n=bd,\ \gcd(a,b)=1$$$.

По лемме $$$\gcd(a^5-b^5,\ ab)=1$$$ (нечётная степень и $$$\gcd(a,b)=1$$$), значит $$$a^5-b^5\mid16$$$. Дальше — малый перебор по делителям $$$16$$$.

Когда почти наверняка сработает ввод GCD

• Симметричные многочлены в $$$x,y$$$ с «классическими» блоками $$$a^2\pm ab+b^2$$$, $$$a^m\pm b^m$$$.
• Уравнения/делимости, где после деления на $$$d$$$ появляется «жёсткий» взаимно-простой множитель.
• Связка gcd/lcm в условии («даны GCD и LCM, «GCD делит/кратно» и т.п.).
• Требования «минимизировать/максимизировать расстояние при фиксированном $$$\gcd$$$»: $$$A=G\cdot u$$$, $$$B=G\cdot v$$$, $$$\gcd(u,v)=1$$$.

Мини-библиотека лемм (на 1–3 строки по Евклиду)

• $$$\gcd(a^2+b^2,\ ab)=\gcd(a^2,\ ab)=1$$$ при $$$\gcd(a,b)=1$$$.
• $$$\gcd(a+b,\ a^2-ab+b^2)=\gcd(a+b,\ 3ab)$$$. При $$$\gcd(a,b)=1$$$ и $$$a+b$$$ не делится ни на $$$a$$$, ни на $$$b$$$, получаем 1.
• $$$\gcd(a^m-b^m,\ a)=\gcd(b^m,\ a)=1$$$ для нечётного $$$m$$$ при $$$\gcd(a,b)=1$$$; аналогично с $$$b$$$.

Задачи CP (где приём «вынести GCD» естественно заходит)

Codeforces

• 1967B1 — Reverse Card (Easy): условие « $$$a+b$$$ кратно $$$b\cdot\gcd(a,b)$$$». Кладём $$$a=du$$$, $$$b=dv$$$, $$$\gcd(u,v)=1$$$ и сводим к делителям/ограничениям на $$$u,v$$$. (Codeforces)
• 1967B2 — Reverse Card (Hard): та же структура, но инвертированная кратность; техника та же, осторожнее с оценками. (Codeforces)
• 992B — Nastya and an Array of GCDs (счёт пар с заданными $$$\gcd$$$ и $$$\mathrm{lcm}$$$): стандартно $$$a=gx,\ b=gy$$$, $$$\gcd(x,y)=1$$$, $$$xy=\frac{\mathrm{lcm}}{g}$$$. Дальше перебор делителей. (Codeforces)
• 1617B — GCD Problem (найти $$$a,b,c$$$ с $$$\gcd(a,b)=c$$$ и $$$a+b+c=n$$$): кладём $$$a=cu,\ b=cv$$$, $$$\gcd(u,v)=1$$$, остаётся разложить $$$n-c=c(u+v)+c$$$. (Codeforces)
• 2043D — GCD Distance (максимизировать $$$|A-B|$$$ при $$$\gcd(A,B)=G$$$ и $$$A,B\in[l,r]$$$): пишем $$$A=G u,\ B=G v,\ \gcd(u,v)=1$$$ и работаем уже внутри отрезка по $$$u,v$$$. (Codeforces)

AtCoder

• ABC177 E — Coprime: проверка «попарная/в совокупности взаимная простота» через gcd и просеивание простых (хорошая разминка к леммам). (AtCoder)
• ARC124 C — LCM of GCDs: аккуратная игра $$$\gcd/\mathrm{lcm}$$$ по пакетам значений; постоянно «вытаскиваем» общие делители и нормализуем. (AtCoder)

Замечания по сложности. После нормализации до $$$\gcd(a,b)=1$$$ перебор чаще всего идёт по делителям одного числа (или по паре делителей, чья композиция фиксирована), т.е. ~$$$O(\tau(n))$$$ или $$$O(\sqrt n)$$$. Это намного быстрее прямого перебора по $$$x,y$$$.