Тема: acm.mipt.ru #140
Всем привет! Помогите разобраться с одним хитрым случаем в этой задаче: Дан порядковый номер числа каталана N(N<=5*10^5), необходимо посчитать его по модулю К (К не обязательно простое, к<=2*(10^9) ). Я решал так -
число каталана C(n) можно записать как дробь a/b = c(n);
a=2n!; b=n!*n!*(n+1);
1) Перепишем это в виде а = b*C(n) и возьмем обе части по модулю к
2) Получим a%k = b%k*ans (ans = c(n)%k - это и есть ответ на задачу)
3) chis = a%k и znam = b%k посчитаем одним циклом, не забывая на каждом шаге брать chis,znam по модулю k
4) Пришли к сравнению znam*ans==chis(mod k)
5) Поделим chis,znam,K на GCD(znam,K) - теперь znam и k взаимно просты и можно применить теорему Эйлера
znam^phi(mod)==1(mod K);
6) найдем ans - из пункта 4 - ans = chis* (1/znam) (mod K) ,
где 1/znam = znam^(phi(mod K)-1) (см. пункт 5)
В степень возводим за логарифм, так как она может достигать 2*(10^9)
А теперь, собственно, хитрый случай: этот метод работает, когда chis!=0 && znam!=0, в противном случае возникает неопределенность вида 0*ans==0(mod K). Кажется, этого можно избежать, если заранее перед пунктом 3 сократить числитель и знаменатель на K (факторизовав К и применив формулу Лежандра) - но как-то не кошерно ради одного случая писать отдельный код, да еще я не уверен на 100%, что это поможет. Кто-нибудь знает, как можно проще обойти этот случай?