前置知识：
数论分块
可以求形如：\(\sum f(i)g(\left \lfloor n/i \right \rfloor )\) 的东西。
原理如下：
比如说求 $\sum_{i=1}^{10}\left \lfloor 10/i \right \rfloor $
得到：10 5 3 2 2 1 1 1 1 1
可以发现有一些块的数值是一样的。
具体一点可以发现 \([l, \left \lfloor \frac{n}{\left \lfloor \frac{n}{l} \right \rfloor } \right \rfloor ]\) 里的数值都是一样的。
又因为这样的值只有 \(\sqrt n\) 个，因此这个式子可以在 \(O(\sqrt n)\) 的复杂度算出来.
int sum(int n)
{
int res = 0;
for (int i = 1,r;i <= n;i = r + 1)
{
r = n/(n/i);
res += ...//计算贡献
}
return res;
}
狄利克雷卷积
一些数论函数:
\(\epsilon (n)\) : \([n=1]\)
\(I(n)\)：任何情况下，\(I(n) = 1\)。
\(id(n)\): \(id(n) = n\)
\(\varphi(n)\) : 欧拉函数， \([1,n]\) 之内与 \(n\) 互质的整数的个数.单点求解欧拉函数
点击查看代码
int get_euler(int n)
{
phi[1] = 1;
for (int i = 2;i <= n;i++)
{
if (!vis[i])
{
prime[cnt++] = i;
phi[i] = i - 1;
}
for (int j = 0;prime[j]<= n/i;j++)
{
vis[prime[j] * i] = 1;
if (i % prime[j] == 0)
{
phi[i*prime[j]] = phi[i] * prime[j];
break;
}
phi[prime[j] * i] = phi[i] * (prime[j]-1);
}
}
return res;
}
莫比乌斯函数 \(\mu\) ：
筛法：
点击查看代码
void euler(int n)
{
mu[1] = 1;
for (int i = 2;i <= n;i++)
{
if (!vis[i]) primes[cnt++] = i,mu[i] = -1;
for (int j = 0;primes[j] <= n / i;j++)
{
int num = i * primes[j];
vis[num] = 1;
if (i % primes[j] == 0)
{
mu[num] = 0;
break;
}
mu[num] = -mu[i];
}
}
}
\(\sigma(n)\) 约数和函数:\(\sigma(n) = \sum _{d|n} d\)。
狄利克雷卷积
\[{\large (f*g)(n) = \sum_{d|n}^{} f(d) \times g(\frac{n}{d})} \]则有：
\[{\large \mu * I = \epsilon} \]\[{\large \varphi * I = id} \]\[{\large \mu * id = \varphi} \]\[{\large f * \epsilon = f} \]\[{\large I * id = \sigma} \]\(\epsilon\) 是单位函数，\(\mu\) 和 \(I\) 互为逆元。
同时可以发现狄利克雷卷积满足交换律、分配律和结合律。
例题1
${\large \mu * I = \epsilon} $
例题2
${\large \varphi * I = id} $
例题3
${\large \mu * I = \epsilon} $
