Задача ШАДа
Даются два натуральных числа k, n (1 <= k <= n <= 500000). Вычислить значения фукнции Эйлера от биномиального коэффициента С(n, k).
Ответ вывести по модулю 1e9 + 7.
Пример k = 1, n = 5, ответ 4.
Ссылка на задачу.

Решение:
Для начало нужно понять, что такое функция Эйлера и как ее находить. Почитать можно по ссылке.

Давайте заранее почитаем все простые числа на отрезке [1, 5e5] это можно сделать с помощью алгоритма Решето Эратосфена за O(n * logn)

Функция Эйлера от числа n будет равен f(n) = n * ( (1-p1)/p1) * ( (1-p2)/p2) * .... * ( (1-pk)/pk)
В нашей задачи вместо n должны подставить C(n, k), давайте для каждого простого числа p узнаем делится ли число C(n, k) на p.

С(n, k) = n!/k!/(n-k)!
пусть
(n!) % (p^cnt1) == 0
(k!) % (p^cnt2) == 0
(n-k)! % (p^cnt3) == 0
Где cnt1, cnt2, cnt3 максимальные целые числа, тогда C(n, k)%p ==0, если cnt1 - cnt2 - cnt3 > 0.

Чтобы найти в какой степени входит простое число в разложение n! применим формулу
cnt1 = n/p + n/(p^2) + ..... + n/(p^t).

Таким образом мы сможем найти все простые делители числа C(n, k), соответственно сможем посчитать f(C(n, k)).

Замечу, что ответ нужно выводить по простому модулю, а значит написать просто ans *= (1-p)/p не получится, так как делить нельзя, но по малой теореме ферма 1/p = p^(1e9 + 7 - 2) mod (1e9 + 7), что соответственно и применим.

Работает за N * log(N), где N = 5e5

Псевдокод в комментариях: