# «Ввод 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>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$.↵
6. **Финишируйте перебором малых вариантов / делителей.** После шага 4 обычно остаётся конечный набор значений (часто — делители простого/почти простого числа), который легко перебрать.↵
↵
---↵
↵
## Четыре показательных скетча↵
↵
### 1) BMO 2017 P1↵
↵
Найти все пары положительных целых $(x,y)$, такие что↵
↵
$$↵
x^3+y^3=x^2+42xy+y^2.↵
$$↵
↵
**Ход:** $x=ad,\ y=bd,\ \gcd(a,b)=1$. Тогда↵
↵
$$↵
d(a+b)(a^2-ab+b^2)=a^2+42ab+b^2.↵
$$↵
↵
Отсюда↵
↵
$$↵
a^2-ab+b^2\mid a^2+42ab+b^2 \ \Rightarrow\ a^2-ab+b^2\mid 43ab.↵
$$↵
↵
Но $\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^4-y^4=p\,(x^3-y^3).↵
$$↵
↵
**Ход:** $x=ad,\ y=bd,\ \gcd(a,b)=1$. Тогда↵
↵
$$↵
d(a+b)(a^2+b^2)=p\,(a^2+ab+b^2).↵
$$↵
↵
Проверкой лемм: $\gcd\big((a+b)(a^2+b^2),\ a^2+ab+b^2\big)=1$. Значит $(a+b)(a^2+b^2)\mid p$, что невозможно для простого $p$ при $a,b>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>0\Rightarrow y>0$. Вводим $x=ad,\ y=bd,\ \gcd(a,b)=1$. Получаем↵
↵
$$↵
d\,(a^2+5b^2)=2021\,b.↵
$$↵
↵
Из $\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$.↵
↵
$$↵
d^3\,(a^5-b^5)=16ab.↵
$$↵
↵
По лемме $\gcd(a^5-b^5,\ ab)=1$ (нечётная степень и $\gcd(a,b)=1$), значит $a^5-b^5\mid16$. Дальше — малый перебор по делителям $16$. и то, что разность 5 степеней растет очень быстро. ↵
↵
---↵
↵
## Когда почти наверняка сработает ввод 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 или 3.↵
* $\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][1])↵
* **1967B2 — Reverse Card (Hard)**: та же структура, но инвертированная кратность; техника та же, осторожнее с оценками. ([Codeforces][2])↵
* **992B — Nastya and an Array of GCDs** (счёт пар с заданными $\gcd$ и $\mathrm{lcm}$): стандартно $a=gx,\ b=gy$, $\gcd(x,y)=1$, $xy=\frac{\mathrm{lcm}}{g}$. Дальше перебор делителей. ([Codeforces][3])↵
* **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][4])↵
* **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][5])↵
↵
**AtCoder**↵
↵
* **ABC177 E — Coprime**: проверка «попарная/в совокупности взаимная простота» через gcd и просеивание простых (хорошая разминка к леммам). ([AtCoder][6])↵
* **ARC124 C — LCM of GCDs**: аккуратная игра $\gcd/\mathrm{lcm}$ по пакетам значений; постоянно «вытаскиваем» общие делители и нормализуем. ([AtCoder][7])↵
↵
**Замечания по сложности.** После нормализации до $\gcd(a,b)=1$ перебор чаще всего идёт по делителям одного числа (или по паре делителей, чья композиция фиксирована), т.е. \~$O(\tau(n))$ или $O(\sqrt n)$. Это намного быстрее прямого перебора по $x,y$.↵
↵
[1]: https://codeforces.me/problemset/problem/1967/B1↵
[2]: https://codeforces.me/problemset/problem/1967/B2↵
[3]: https://codeforces.me/problemset/problem/992/B↵
[4]: https://codeforces.me/problemset/problem/1617/B↵
[5]: https://codeforces.me/problemset/problem/2043/D↵
[6]: https://atcoder.jp/contests/abc177/tasks/abc177_e↵
[7]: https://atcoder.jp/contests/arc124/tasks/arc124_c↵
↵
В задачах с двумя (или несколькими) целочисленными переменными часто выгодно «вынести» их общий делитель:↵
пусть $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>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$.↵
*
6. **Финишируйте перебором малых вариантов / делителей.** После шага 4 обычно остаётся конечный набор значений (часто — делители простого/почти простого числа), который легко перебрать.↵
↵
---↵
↵
## Четыре показательных скетча↵
↵
### 1) BMO 2017 P1↵
↵
Найти все пары положительных целых $(x,y)$, такие что↵
↵
$$↵
x^3+y^3=x^2+42xy+y^2.↵
$$↵
↵
**Ход:** $x=ad,\ y=bd,\ \gcd(a,b)=1$. Тогда↵
↵
$$↵
d(a+b)(a^2-ab+b^2)=a^2+42ab+b^2.↵
$$↵
↵
Отсюда↵
↵
$$↵
a^2-ab+b^2\mid a^2+42ab+b^2 \ \Rightarrow\ a^2-ab+b^2\mid 43ab.↵
$$↵
↵
Но $\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^4-y^4=p\,(x^3-y^3).↵
$$↵
↵
**Ход:** $x=ad,\ y=bd,\ \gcd(a,b)=1$. Тогда↵
↵
$$↵
d(a+b)(a^2+b^2)=p\,(a^2+ab+b^2).↵
$$↵
↵
Проверкой лемм: $\gcd\big((a+b)(a^2+b^2),\ a^2+ab+b^2\big)=1$. Значит $(a+b)(a^2+b^2)\mid p$, что невозможно для простого $p$ при $a,b>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>0\Rightarrow y>0$. Вводим $x=ad,\ y=bd,\ \gcd(a,b)=1$. Получаем↵
↵
$$↵
d\,(a^2+5b^2)=2021\,b.↵
$$↵
↵
Из $\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$.↵
↵
$$↵
d^3\,(a^5-b^5)=16ab.↵
$$↵
↵
По лемме $\gcd(a^5-b^5,\ ab)=1$
↵
---↵
↵
## Когда почти наверняка сработает ввод 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 или 3.↵
* $\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][1])↵
* **1967B2 — Reverse Card (Hard)**: та же структура, но инвертированная кратность; техника та же, осторожнее с оценками. ([Codeforces][2])↵
* **992B — Nastya and an Array of GCDs** (счёт пар с заданными $\gcd$ и $\mathrm{lcm}$): стандартно $a=gx,\ b=gy$, $\gcd(x,y)=1$, $xy=\frac{\mathrm{lcm}}{g}$. Дальше перебор делителей. ([Codeforces][3])↵
* **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][4])↵
* **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][5])↵
↵
**AtCoder**↵
↵
* **ABC177 E — Coprime**: проверка «попарная/в совокупности взаимная простота» через gcd и просеивание простых (хорошая разминка к леммам). ([AtCoder][6])↵
* **ARC124 C — LCM of GCDs**: аккуратная игра $\gcd/\mathrm{lcm}$ по пакетам значений; постоянно «вытаскиваем» общие делители и нормализуем. ([AtCoder][7])↵
↵
**Замечания по сложности.** После нормализации до $\gcd(a,b)=1$ перебор чаще всего идёт по делителям одного числа (или по паре делителей, чья композиция фиксирована), т.е. \~$O(\tau(n))$ или $O(\sqrt n)$. Это намного быстрее прямого перебора по $x,y$.↵
↵
[1]: https://codeforces.me/problemset/problem/1967/B1↵
[2]: https://codeforces.me/problemset/problem/1967/B2↵
[3]: https://codeforces.me/problemset/problem/992/B↵
[4]: https://codeforces.me/problemset/problem/1617/B↵
[5]: https://codeforces.me/problemset/problem/2043/D↵
[6]: https://atcoder.jp/contests/abc177/tasks/abc177_e↵
[7]: https://atcoder.jp/contests/arc124/tasks/arc124_c↵
