Условия про НОД и НОК

Замечание.

На реальных олимпиадах обычно в условии задачи указывают считать пары неупорядоченными, то есть считать одинаковыми пары и при В условии данной задачи этого указано не было. Однако жюри при проверке предлагается засчитывать как верные решения, учитывающие порядок чисел в паре, так и верные решения, рассматривающие только неупорядоченные пары.

_________________________________________________________________________________________________________________________________________________________________________________

Рассмотрим два случая

• Хотя бы одно из чисел равно 5000.

  Тогда другое число может быть любым делителем числа 5000. Поскольку , оно имеет делителей. Таким образом, в этом случае имеется 20 пар без учёта порядка в паре и упорядоченных пар (так как среди 20 в одной паре числа совпадают и пара не поменяется при их перестановке).

• Ни одно из двух чисел не равно 5000.

  Тогда в разложении одного из этих чисел на простые сомножители должен присутствовать множитель , а в разложении другого — множитель Без учёта порядка в паре положим

  

  где и независимо от этого Таким образом, в этом случае имеется неупорядоченных пар (и соответственно 24 упорядоченные пары, поскольку в каждой из 12 пар числа различны).

_________________________________________________________________________________________________________________________________________________________________________________

Итак, есть пары без учёта порядка и пары с учётом порядка.