版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
title: "题解 - [Luogu P5221] Product" categories:
${\rm CYJian}$: "听说 $gcd$ 和 $\sum$ 套起来比较好玩？？那我就......"
${\rm CYJian}$ 最近闲的玩起了 $gcd$. 他想到了一个非常简单而有意思的式子:
$$ \prod{i=1}^N\prod{j=1}^N\frac{lcm(i,j)}{gcd(i,j)}\ (\bmod\ 104857601) $$
${\rm CYJian}$ 已经算出来这个式子的值了. 现在请你帮他验算一下吧. ${\rm CYJian}$ 只给你 $0.2s$ 的时间哦
一行一个正整数 $N$
一行一个正整数, 表示答案模 $104857601$ 的值
5
585494
样例解释:
| $\frac{lcm}{gcd}$ | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 1 | 1 | 2 | 3 | 4 | 5 |
| 2 | 2 | 1 | 6 | 2 | 10 |
| 3 | 3 | 6 | 1 | 12 | 15 |
| 4 | 4 | 2 | 12 | 1 | 20 |
| 5 | 5 | 10 | 15 | 20 | 1 |
对于 $30\%$ 的数据: $1 \leq N \leq 5000$
对于 $100\%$ 的数据: $1 \leq N \leq 1000000$
推式子
$$ \begin{aligned} \prod{i=1}^n\prod{j=1}^n \frac{ij}{(i,j)^2} & =\frac{(n!)^{2n}}{\prod{i=1}^n\prod{j=1}^n(i,j)^2} \ & =\frac{(n!)^{2n}}{\prod{d=1}^nd^{2\sum{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum{j=1}^{\lfloor\frac{n}{d}\rfloor}[(i,j)=1]}} \ & =\frac{(n!)^{2n}}{\prod{d=1}^nd^{2\sum_{e=1}^{\lfloor\frac{n}{d}\rfloor}\mu(e)\lfloor\frac{n}{de}\rfloor^2}} \ \end{aligned} $$
两层整除分块即可
$O(n)$