Я решил с помощью ДП: f[i,k,d]-число способов выбрать k чисел от i до s, нод которых d.
Работает 0.031 sec.
Вопрос: как решить эту задачу именно с помощью теории чисел( я использовал в динамике только один факт: gcd(a1,a2,...,ak)=gcd(a1,gcd(a2,...,ak)))?

Актуально ли это) но здесь можно решать еще с помощью формулуы включений-исключений. Предподсчитаем простые числа. Признаки в формуле - делимость на i. сочетаниями подсчитаем кол-во способов выбрать наборы. сочетания посчитаем динамикой