|
|
вернуться в форумAC,but have question Я решил с помощью ДП: f[i,k,d]-число способов выбрать k чисел от i до s, нод которых d. Работает 0.031 sec. Вопрос: как решить эту задачу именно с помощью теории чисел( я использовал в динамике только один факт: gcd(a1,a2,...,ak)=gcd(a1,gcd(a2,...,ak)))? Re: AC,but have question Послано Rzxy1 30 дек 2021 12:57 Актуально ли это) но здесь можно решать еще с помощью формулуы включений-исключений. Предподсчитаем простые числа. Признаки в формуле - делимость на i. сочетаниями подсчитаем кол-во способов выбрать наборы. сочетания посчитаем динамикой |
|
|