Илья выписал на доску все делители числа , затем соединил линией каждые два числа, наибольший общий делитель которых больше 1. Сколько линий нарисовал Илья?

1. Дано

Нам дано число $N = 2^{10} \cdot 5^{5}$. Илья выписал на доску все делители этого числа. Линией соединяются каждые две числа, наибольший общий делитель (НОД) которых больше 1.

2. Найти

Требуется найти общее количество нарисованных линий.

3. Решение

Общее количество линий, которые можно провести между всеми парами чисел, равно общему числу пар. Если у нас есть $K$ чисел, общее количество пар равно числу сочетаний из $K$ по 2, то есть $\binom{K}{2}$.

Линии проводятся только между теми парами, у которых $\text{НОД}(a, b) > 1$. Это означает, что $a$ и $b$ должны и...