为什么模数是偶数我都敢先取模后除以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)$