卢卡斯定理

[Xeonacid]

https://oi-wiki.org/math/lucas/

OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛

[guodong2005]

这个exlucas写得好简陋

[abc1763613206]

@guodong2005 欢迎参与贡献~

[Mizuhara-yaguchi]

这个exlucas写的稀烂

[Mizuhara-yaguchi]

私自更正了一下编主的板子，主要问题在循环变量要用ll，以及某处s * i % P的i要提前%P
ll CRT(int n, ll* a, ll* m) {
ll M = 1, p = 0;
for (int i = 1; i <= n; i++) M = M * m[i];
for (int i = 1; i <= n; i++) {
ll w = M / m[i], x, y;
exgcd(w, m[i], x, y);
p = (p + a[i] * w * x % M) % M;
}
return (p % M + M) % M;
}
ll calc(ll n, ll x, ll P) {
if (!n) return 1;
ll s = 1;
for (ll i = 1; i <= P; i++)
if (i % x) s = s * i % P;
s = ksm(s, n / P, P);
for (ll i = n / P * P + 1; i <= n; i++)
if (i % x) s = i % P * s % P;
return s * calc(n / x, x, P) % P;
}
ll multilucas(ll n, ll m, ll x, ll P) {
if (n < m) return 0;
int cnt = 0;
for (ll i = n; i; i /= x) cnt += i / x;
for (ll i = m; i; i /= x) cnt -= i / x;
for (ll i = n - m; i; i /= x) cnt -= i / x;
return ksm(x, cnt, P) % P * calc(n, x, P) % P * a_1(calc(m, x, P), P) %
P * a_1(calc(n - m, x, P), P) % P;
}
ll exlucas(ll n, ll m, ll P) {
int cnt = 0;
ll p[20], a[20];
for (ll i = 2; i * i <= P; i++) {
if (P % i == 0) {
p[++cnt] = 1;
while (P % i == 0) p[cnt] = p[cnt] * i, P /= i;
a[cnt] = multilucas(n, m, i, p[cnt]);
}
}
if (P > 1) p[++cnt] = P, a[cnt] = multilucas(n, m, P, P);
return CRT(cnt, a, p);
}

[Enter-tainer]

@Mizuhara-yaguchi 你好，如果你有好的想法或者建议，欢迎开 pull request 帮助修复，或者开 issue 指出

[xyf007]

exLucas 的复杂度是什么？

[Mizuhara-yaguchi]

oi wiki上给的写法实际上是单次询问O(plogp)的。而通过预处理(n!/(n以内的p的所有倍数的乘积))%p，可以使时间复杂度优化至单次O(p + logp)。而如果p是固定的，我们在一开始就可以对p进行分解，并进行预处理，可以达到总复杂度O(p + Tlogp)。以上所计算复杂度均没有考虑excrt的复杂度，需乘上。

…

------------------&nbsp;原始邮件&nbsp;------------------ 发件人: "OI-wiki/gitment" <[email protected]&gt;; 发送时间:&nbsp;2020年7月30日(星期四) 上午9:31 收件人:&nbsp;"OI-wiki/gitment"<[email protected]&gt;; 抄送:&nbsp;"刘知源"<[email protected]&gt;;"Mention"<[email protected]&gt;; 主题:&nbsp;Re: [OI-wiki/gitment] 卢卡斯定理 - OI Wiki (#375) exLucas 的复杂度是什么？ — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or unsubscribe.

[wanzzhehe]

我算是知道扩展卢卡斯那里为什么要用例子了，自己尝试用公式总结的时候快把自己玩死了

[Shiro-nagi]

在分解模数$P=p_1^{a_1}*...*p_k^{a_k}$ 之后, 直接开 k 个 n大小的数组,
直接对于每个$p_i$线性推一遍 1~n的 阶乘 和 逆元 和 逆元的阶乘
最多也就 20 个质因子吧, 这样做是时空复杂度高了很多吗?

[YOYO-UIAT]

扩展 Lucas 的时间复杂度为啥用的是 log 而不是 \log，好丑

[anf4108]

这个a和$alpha$放一起。。。看了半天才看出来不一样