Дано число n = 2^100 * 3^100. Сколько существует делителей числа n^2, которые меньше n, но не являются делителями n?
Задача: n = 2^100 · 3^100. Найти количество делителей n^2, которые меньше n, но не делят n.
Пусть n = p^a q^b, где p=2, q=3, a=b=100. Тогда n^2 = p^{2a} q^{2b} = 2^{200} 3^{200}.
Сколько делителей имеет n^2? Делителей n^2: τ(n^2) = (2a+1)(2b+1) = (200+1)(200+1) = 201·201 = 40401.
Сколько делителей n меньше n? Делители n формируются как 2^i 3^j с 0 ≤ i ≤ a и 0 ≤ j ≤ b. Их количество τ(n) = (a+1)(b+1) = 101·101 = 10201. Дельный факт: среди делителей n ровно один равен n itself, следовательно делителей n, меньших n, ровно τ(n) − 1 = 10201 − 1 = 10200.
Сколько делителей n^2 меньше n? Делители n^2 и их "пары" по отношению к n^2: если d — делитель n^2 и d ≠ n, то либо d < n, либо d > n, и пары (d, n^2/d) образуют одно меньшeе n и одно большее n. Следовательно число делителей n^2, меньших n, равно (τ(n^2) − 1)/2 = (40401 − 1)/2 = 40400/2 = 20200.
Искомые делители — это делители n^2, меньше n, которые не делят n. Количество таких делителей равно 20200 − 10200 = 10000.
Ответ: 10000.
Дополнительная заметка (обобщение): если n = p^a q^b, то число делителей n^2, меньших n и не делящих n, равно a·b. В нашем случае a=b=100, поэтому результат равен 100·100 = 10000.
