「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}\)
为什么模数是偶数我都敢先取模后除以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}\)
给出 \(n,k\) 求
\[\sum_{i=1}^n\sum_{j=1}^n sgcd(i,j)^k\]
其中 \(sgcd(i,j)\) 表示 \(i,j\) 的次大公约数,特殊地,\(sgcd(1,1)=0\)
对 \(2^{32}\) 取模
\(n\le 10^9, k\le 50\)
令 \(\sigma_0(n)\) 表示 \(n\) 的约数个数
求 \[\sum_{i=1}^n \sigma_0(i^3)\]
\(n\le 10^{11}\)
令 \(\sigma_0(n)\) 表示 \(n\) 的约数个数
求 \[\sum_{i=1}^n \sigma_0(i^2)\]
\(n\le 10^{12}\)
大家都会啊,还是一次考试题的部分分,听 ftq 讲了
咕了几天就来学了
好像比杜教筛少很多思维难度吧
update:
好难啊,重新理解了好多次,还改了文章结构
如果一个积性函数 \(f(i)\) 在 \(i\) 是质数时是一个关于 \(i\) 的低次多项式,并且在质数的幂处的能快速求,那么大概可以用Min_25筛来求
\[\sum_{i=1}^n f(i)\]
对于 \(f(1)\) 特判
时间复杂度 \(\mathcal O(\frac{n^\frac{3}{4}}{\log n})\),空间复杂度\(\mathcal O(\sqrt{n})\)
并且同时我们可以求出每个 \(\lfloor \frac{n}{x} \rfloor\) 的 \(\sum\limits_{i=2}^{\lfloor \frac{n}{x} \rfloor}[\text{$i$ 是质数}]f(i)\)