为什么模数是偶数我都敢先取模后除以2了。不知道是不是傻了。

51nod 1965

题意

求

\[\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}\)

51nod 1847

题意

给出 \(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\)

SPOJ APS2

题意

令 \(f(i)\) 表示 \(i\) 的最小质因子

求 \[\sum_{i=2}^n f(i)\]

\(n\le 1.234567891011*10^{12}\)

题意

令 \(\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)\)