Lucas 了解一下?
by Union_Find @ 2024-04-29 12:48:54
@[luuia](/user/557800) 用类似 exlucas 的方式对 p 质因数分解然后 crt 合并吧。
by diqiuyi @ 2024-04-29 13:06:19
@[Union_Find](/user/958944) @[diqiuyi](/user/324666) $p \le 20^9$
by luuia @ 2024-04-29 13:38:38
分解质因数都是 $O(\sqrt{p})$ 的肯定过不了啊
by luuia @ 2024-04-29 13:39:32
@[luuia](/user/557800) $\sqrt{p}$ 才大概 $6\times 10^5$ 啊。
by diqiuyi @ 2024-04-29 13:53:01
实在不行使用 pollard rho
by diqiuyi @ 2024-04-29 13:55:20
@[diqiuyi](/user/324666) 如果 $p$ 是一个大质数怎么处理
by luuia @ 2024-04-29 14:13:16
@[luuia](/user/557800) $n,m,x,y$ 都很小,可以直接算啊。分解质因数是因为有可能没有逆元。
by diqiuyi @ 2024-04-29 18:36:02
另外,普通的质因数分解其实可以是 $O(\sqrt{p}/\log{p})$ 的。
by diqiuyi @ 2024-04-29 19:50:22
@[diqiuyi](/user/324666) 明白了 跟我一开始的思路差不多 感谢 已关
by luuia @ 2024-04-29 20:57:17