简单的近线性做法

P5221 Product

@[蒟蒻君HJT](/user/131591) 已经加入审核队列(
by LeavingZ @ 2023-02-24 23:46:45


@[蒟蒻君HJT](/user/131591) 以及要在 LaTeX 里面打大括号可以 `$\{qwq\}$` $\{qwq\}$
by LeavingZ @ 2023-02-24 23:51:39


Ciallo~(∠・ω< )⌒☆
by Remilia1023 @ 2023-02-25 01:33:14


实际上 $1\sim n$ 中能表示成 $p^k$ 的数只有 $O(\frac{n}{\log n})$ 个,因此如果使用线性求逆元复杂度即严格线性。
by zhouyuhang @ 2023-02-25 07:02:10


这个东西我曾经也写过。。。<https://www.luogu.com.cn/blog/myee/solution-p5221>。
by myee @ 2023-02-25 08:30:00


不过按现在的标准来看题解格式可能就不规范了。
by myee @ 2023-02-25 08:30:32


|