数论:带模除法/逆元/费马小定理

今天做百度之星,做砸了,卡在一道硬货上,但是赛后请教群牛涨了姿势,赶紧记录。

题目收录在 HDU http://acm.hdu.edu.cn/showproblem.php?pid=4828

题目最终是这样:要求 Catalan(n) MOD 1000000007,但是最大的 n 要去到 1000000 这个数量级,查询 100000 次。

无疑,要用极高的效率去解这道题,预先打好这个表。

这里先加个小小的插曲,其实我连 Catalan 函数都不熟悉,当时我是用蛮力打了前面几个数,然后用 OEIS 查找序列找出来的这是一个 Catalan 函数,可见 OEIS 确乃神器也。

然后关键在于生成,可以确认到最简单的方法是:

Catalan(n+1) = Catalan(n) * (4*n+2) / (n+2) (mod M)

能直接算当然好,但是我之前不会带模除法,只好用大数打表,结果打出来的表太巨大(脚趾头都算得出来)。

最终的解法是用费马小定理求逆元。

意思是,带模的除法:求 a / b = x (mod M)

只要 M 是一个素数,而且 b 不是 M 的倍数,就可以用一个逆元整数 b’,通过 a / b = a * b' (mod M),来以乘换除。

费马小定理说,对于素数 M 任意不是 M 的倍数的 b,都有:

b ^ (M-1) = 1 (mod M)

于是可以拆成:

b * b ^ (M-2) = 1 (mod M)

于是:

a / b = a / b * (b * b ^ (M-2)) = a * (b ^ (M-2)) (mod M)

也就是说我们要求的逆元就是 b ^ (M-2) (mod M)

真是涨姿势了。

这样在求 (2*n+1) ^ (M-2) (mod M) 可以在 log(M-2) 的时间内计算出来的条件下,打完这个表只需要 1000000 * log(M-2) 的时间,足够快了!

可惜题还是没有做得出来,比赛还是挂了。

但是这一招很有用,通过这个,其实在一个 (mod M) 的群里面,乘法除法完全是可以双向步进的,有了这个强力的数论算法,技术又有长进了。

 


【转载请附】愿以此功德,回向 >>

原文链接:https://www.huangwenchao.com.cn/2014/05/mod-div.html【数论:带模除法/逆元/费马小定理】

《数论:带模除法/逆元/费马小定理》有2个想法

  1. 涨姿势了,前两天做UVa 1478 – Delta Wave,跑了2s+; 是同一个题(⊙⊙),开了5000的数组才过╮(╯▽╰)╭; 原来可以这样搞(⊙⊙),大黄Orz~。

发表评论

电子邮件地址不会被公开。 必填项已用*标注