非常大火 谁能想到模板题要整骚操作用递归过
by ming2023 @ 2023-12-21 16:04:13
@[ming2023](/user/1103464) 他们又没说费马小定理是正解好吗，题解又不是只能给正确思路。
by xiaoshumiao @ 2023-12-21 16:11:55
@[xiaoshumiao](/user/1008513) 过不了那放出来干什么 也不说是错误解法
by ming2023 @ 2023-12-21 16:23:14
@[ming2023](/user/1103464) 那也是一种方法！不能多学点东西吗？
by xiaoshumiao @ 2023-12-21 16:24:28
@[xiaoshumiao](/user/1008513) 好吧...
by ming2023 @ 2023-12-21 16:26:08
在进行分数取模时会用到乘法逆元，如果$ax\equiv1\pmod{n}$中的 a 是随机的或 $a \ge 10^9$时扩欧和费马小定理的速度较快，而线性递推就会慢很多
by _zuoqingyuan @ 2023-12-22 17:33:11
只能说日常做题更多会用扩欧或费马小定理，这两种方法的时间都很优异，只是这道题时限就500ms，所以被卡了。线性递推虽然能过这题，但也仅限于解决 a 较小的问题了，不适于分数取模
by _zuoqingyuan @ 2023-12-22 17:36:35