「51nod 1965」奇怪的式子
为什么模数是偶数我都敢先取模后除以2了。不知道是不是傻了。
题意
求
\[\prod_{i=1}^n \sigma_0(i)^{\mu(i)+i} \mod(10^{12}+39)\]
其中 \(\sigma_0(i)\) 表示 \(i\) 的正约数个数,\(10^{12}+39\) 是质数
\(n\le 10^{11}\)
做法
\[ \prod_{i=1}^n \sigma_0(i)^{\mu(i)+i} = \prod_{i=1}^n \sigma_0(i)^i \prod_{i=1}^n \sigma_0(i)^{\mu(i)} \]
两部分可以分开来做
一
考虑每个质数的贡献
\[ \prod_{i=1}^n \sigma_0(i)^i = \prod_{p\text{是质数}} \prod_{p^i\le n} (i+1)^{f(\lfloor \frac{n}{p^i} \rfloor) * p^i - f(\lfloor \frac{n}{p^{i+1}} \rfloor) * p^{i+1}} \]
其中 \(f(x)=\sum\limits_{i=1}^x i=\frac{x(x+1)}{2}\)
对于 \(p\le \sqrt{n}\) 枚举 \(p\) 计算贡献
对于 \(p>\sqrt{n}\),指数只能为 \(1\)
于是贡献为
\[ \prod_{p>\sqrt{n},p\text{是质数}} 2^{f(\lfloor \frac{n}{p} \rfloor) * p} \]
用Min_25筛出对于每一个 \(\lfloor \frac{n}{x} \rfloor\) 的 \(\sum\limits_{i=1}^{\lfloor \frac{n}{x} \rfloor} [i\text{是质数}] * i\)
分块计算即可
二
要求 \(\prod\limits_{i=1}^n \sigma_0(i)^{\mu(i)}\)
可以发现对于有平方因子的 \(i\) ,\(\mu(i)=0\),所以没有贡献
令 \(g(i)\) 表示 \(i\) 的质因子数
\[ \begin{align} & \prod_{i=1}^n \sigma_0(i)^{\mu(i)} \\ = & \prod_{i=1}^n 2^{\mu(i)g(i)} \\ = & 2^{\left(\sum_{i=1}^n \mu(i)g(i)\right)} \end{align} \]
考虑怎么求 \(\sum\limits_{i=1}^n \mu(i)g(i)\)
令
\[ \begin{align} F(a,b)&=\sum_{i=2}^a [i\text{是质数 或 } pmin_i\ge prime_b] * \mu(i) \\ S(a,b)&=\sum_{i=2}^a [i\text{是质数 或 } pmin_i\ge prime_b] * \mu(i)g(i) \end{align} \]
其中 \(pmin_i\) 表示 \(i\) 的最小质因子,\(prime_i\) 表示第 \(i\) 个质数
于是可以用Min_25筛转移
\[ \begin{align} F(a,b)&=F(a,b+1)-\left(F(\lfloor \frac{a}{prime_b} \rfloor,b+1)+b\right) \\ S(a,b)&=S(a,b+1)-\left(S(\lfloor \frac{a}{prime_b} \rfloor,b+1)+F(\lfloor \frac{a}{prime_b},b+1)+2b\right) \end{align} \]
注意这里的模数有点大,需要用快速乘
总复杂度 \(\mathcal O(\frac{n^{\frac{3}{4}}}{\log n})\)
代码
1 |
|
「51nod 1965」奇怪的式子