积性函数:
积性函数定义ok
积性函数指对于所有互质的整数(a)和(b)有性质(f(ab)=f(a)f(b))的数论函数
除数函数?
莫比乌斯函数(mu)ok
为什么是积性函数?
对任意(a,b,gcd(a,b)=1), (ab)的质因子集合可以不重不漏分到(a,b)的质因子集合中
分类讨论一下,满足定义
欧拉函数(phi)ok
小于等于(n)的数中与(n)互质的数的数目
通式:
通式的意义:把他展开, 相当于做容斥, 筛除的所有(n)因数
为什么是积性函数?
对任意(a,b,gcd(a,b)=1), (a,b)没有不含有相同的(p), 直接带入通式得证
反正关于欧拉函数的东西盯着这个通式就好了
幂函数(Id)ok
(id_k(n)=n^k)
(id(n)=id_1(n)=n)
显然是积性函数
单位函数(epsilon)ok
(epsilon(n)=[n=1])
显然是积性函数
线性筛
核心:保证每个数只被他最小的质数筛到一次
int tot;
bool vis[MAXN];
int p[MAXN], phi[MAXN], mu[MAXN];
void filter()
{
phi[1] = mu[1] = 1;
for (int i = 2; i <= n; ++ i)
{
if (!vis[i]) p[++ tot] = i, phi[i] = i - 1, mu[i] = -1;
for (int j = 1; j <= tot && i * p[j] <= n; ++ j)
{
vis[i * p[j]] = true;
if (i % p[j] == 0)
{
phi[i * p[j]] = phi[i] * p[j]; mu[i * p[j]] = 0;
//没有增加质因子, 结合phi的通式可得
break;
}
else
{
phi[i * p[j]] = phi[i] * phi[p[j]];
mu[i * p[j]] = -mu[i];
}
}
printf("%d %d
", mu[i], phi[i]);
}
}
Dirichlet卷积
交换律 (f ∗ g = g ∗ f)
结合律 ((f ∗ g) ∗ h = f ∗ (g ∗ h))
分配律 (f ∗ (g + h) = f ∗ g + f ∗ h)
单位元 (f ∗ ϵ = f)
若 (f,g) 均为积性函数，则 (f*g) 也是积性函数
证明：
对任意(a,b,gcd(a,b)=1), (ab)的质因子集合可以不重不漏分到(a,b)的质因子集合中
((f*g)(ab) = sum_{d|ab}f(d)g(frac{ab}{d}))
设(d=d_a*d_b), (d_a,d_b)分别由(a,b)的因子组成, 显然组成的方式唯一, 并且(d)唯一分解成(d_a,d_b)
已知(f,g),(O(nlog_2^n))求((f*g))
for (int i = 1; i * i <= n; ++ i)
{
(f*g)[i*j] += f[i] * g[i];
for (int j = i + 1; i * j <= n; ++ j)
(f*g)[i*j] += f[i] * g[j] + f[j] * g[i];
}
不会证
常见数论函数
(sigma(n))表示整数(n)的所有正因数的和
( au(n))表示整数(n)的所有正因数的个数
(Id(i)=i)
以及前面的一些积性函数
常见狄利克雷卷积及其证明
(epsilon = mu *1)
证明:
(n)含有多个相同质因子或(=1)是显然成立
考虑(n=p_1*p_2*...*p_k), (p_i)都是不同质因子
由于((x+y)^k=sum x^iy^{k-i}*inom{k}{i}), 带入(x=-1, y=1), 凑进去
(sigma = Id*1)
( au=1*1)
显然
(phi = mu * Id)
证明:
(phi * 1= Id)
上面一个等式两边同乘以(1)
莫比乌斯Van演
定理:(epsilon = mu * 1)
若函数 (f, g) 满足
(f(n) = sum_{d|n}g(d))
则
(g(n) = sum_{d|n}mu(d)f(frac{n}{d}) = sum_{d|n}mu(frac{n}{d})f(d))
证明:$
(f = g*1 longleftrightarrow mu * f = g) $
左式同乘以(mu), 右式同乘以(1)
常用:
运用这个卷积:
(epsilon = mu * 1) 即 (sum_{d|n}mu(d) = 1)
([gcd(i, j) == 1] = sum_{k | gcd(i,j)} mu(k))
例题:
NOI2015寿司
BZOJ1257: CQOI2007余数之和
题意:
(n, k(le10^9)), 求(sum_{i=1}^{n}(k mod i))
Sol:
(sum_{i=1}^{n}(k mod i) = sum_{i=1}^{n}(k - k / i * i) = nk - sum_{i=1}^{n}(k/i)*i)
BZOJ1101: POI2007Zap
(T) 组询问，(1 ≤ T, n, m , d≤ 50000)
相当于求
n /= d, m /= d 根据(epsilon = mu * 1),即求
除法分块(O(sqrt{n}))
BZOJ2154: Crash的数字表格
(1le n, mle10^7), 求
(i*j=gcd(i,j) * lcm(i,j))
设(p=g*d)
完了,然后怎么做?
大爷xyyxyyx说: (F(p)=sum_{d|p}d*mu(d)*p)是积性函数
为什么?
设(a,b,gcd(a,b)=1,d=da*db,da|a,db|b)
好了, 然后(O(n))筛?然后暴力(O(n))求答案?
观察(F(i))的式子, 套用线性筛:
- (i)为质数: (F(i)=(1*mu(1)+i*mu(i))*i)
- 用已经筛出来的质数(p[j])去筛(i*p[j])
- (imod p[j]!=0), 互质!(F(i*p[j])=F(i)*F(p[j]))
- (i mod p[j] == 0),考虑对比(F(i)),新加入的因数必须含有(p^2), 而这样的因数(mu{})是等于0的!那么直接(F(i*p[j])=F(i)*p[j])
然后少写了一个(mod), WA了,然后又T了
整出分块!!注意到在一段区间里((n/p, m/p))是不变的, 所以可以对(F)直接区间求和(前缀和实现)
//空间注意一点
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 1e7 + 10;
const LL MOD = 20101009;
int n, m;
LL ans;
int tot;
bool vis[MAXN];
int mu[MAXN], p[664590];
LL f[MAXN];
int sum[MAXN], sumf[MAXN];
void filter()
{
mu[1] = sumf[1] = f[1] = sum[1] = 1;
LL tmp1 = 0;
for (int i = 2; i <= m; ++ i)
{
tmp1 = 1LL * i * (i + 1) / 2 % MOD;
sum[i] = tmp1;
if (!vis[i]) mu[i] = -1, p[++ tot] = i, f[i] = 1LL * (1 + i * mu[i] % MOD + MOD) * i % MOD;
for (int j = 1; j <= tot && i * p[j] <= m; ++ j)
{
vis[i * p[j]] = true;
if (i % p[j] == 0) { mu[i * p[j]] = 0; f[i * p[j]] = f[i] * p[j] % MOD; break; }
else mu[i * p[j]] = -mu[i], f[i * p[j]] = f[i] * f[p[j]] % MOD;
}
sumf[i] = (sumf[i - 1] + f[i]) % MOD;
}
}
int main()
{
scanf("%d%d", &n, &m);
if (n > m) swap(n, m);
filter();
for (int i = 1; i <= n; )
{
int r = min(n, min(n / (n / i), m / (m / i)));
(ans += sum[n / i] % MOD * sum[m / i] % MOD * (sumf[r] - sumf[i - 1] + MOD) % MOD) %= MOD;
i = r + 1;
}
printf("%lld
", ans);
return 0;
}
PE530: GCD of Divisors
Let f(n) be the sum of the greatest common divisor of d and n/d over all positive divisors d of n, that is (f(n)=displaystylesumlimits_{d|n}\, ext{gcd}(d,frac n d))
Let F be the summatory function of f, that is (F(k)=displaystylesumlimits_{n=1}^k \, f(n))
You are given that (F(10)=32) and (F(1000)=12776.)
Find (F(1015)).
提交答案题
相当于枚举(i), 并将(i)分解成两个数的乘积, 求所有这样的(gcd)的和
等价于枚举两个数, 他们乘积(le n), 求他们(gcd)的乘积
所以:
注意不能像以前那样把两个(sum{})的上界除以(g)
从而认为(i*jle n/g)
因为两个(sum{})是有关联的,只有当第一个确定时,才能枚举第二个, 如果这么做的话相当于同时枚举两个
例如(i*jle n*n/i)显然不对
那么继续
考虑把(g*d)并在一起, 然后康康这个和什么卷积比较像
于是就化简成了
什么,要求(10^{15})?不会炸空间吗?
注意后面(lfloor frac{n}{p^2} floor), 可以缩小到(sqrt{n})
那么枚举(p), 然后每次单独分块求就好了
复杂度呢?前半个(O(sqrt{n})), 后半个(O(ln_n))?不会证...
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 32e6 + 10;
const LL MOD = 20101009;
LL n;
LL ans;
int tot;
bool vis[MAXN];
LL p[MAXN], phi[MAXN];
LL f[MAXN];
void filter()
{
phi[1] = 1;
for (int i = 2; i < MAXN; ++ i)
{
if (!vis[i]) p[++ tot] = i, phi[i] = i - 1;
for (int j = 1; j <= tot && i * p[j] < MAXN; ++ j)
{
vis[i * p[j]] = true;
if (i % p[j] == 0) { phi[i * p[j]] = phi[i] * p[j]; break; }
else phi[i * p[j]] = phi[i] * phi[p[j]];;
}
}
}
LL calc(LL x)
{
LL ret = 0;
for (LL i = 1; i <= x; )
{
LL r = min(x / (x / i), x);
ret += (r - i + 1) * (x / i);
i = r + 1;
}
return ret;
}
int main()
{
scanf("%lld", &n);
n = 1e15;
filter();
for (LL i = 1; i * i <= n; ++ i)
{
ans += phi[i] * calc(n / (i * i));
}
printf("%lld
", ans);
return 0;
}
杜教筛
基本
目的:求(f(i))的前缀和
套路:构造(h=g*f)
即等同于枚举两个因数，他们乘积(le n),计算他们(g)和(f)的乘积的和
设(S(n)=sum f(i))
所以只要凑出方便的(h, g)就可以套用最后一行式子了
求(sum_{i=1}^{n}mu(i))
(epsilon = mu * 1, h=epsilon,g=1)
求(sum_{i=1}^{n}phi(i))
(Id=phi*1, h=Id, g=1)
先看一道例题
例题BZOJ3944: Sum
(T(le 10))组数据, (N(le 2^{31}-1)), 求(sum_{i=1}^{n}mu(i), sum_{i=1}^{n}phi(i))
两个长得很像可以一起做, (lfloorfrac{n}{i} floor)可以整除分块
递归实现, 但是要先预先筛一部分, 不然会(T), 记忆化搜索用(map)记录
#include <cstdio>
#include <map>
using namespace std;
typedef long long LL;
typedef pair<int, LL> PIL;
#define mkpr make_pair
const int MAXN = 5e6 + 2;
inline LL in()
{
LL x = 0, flag = 1; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') flag = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
return x * flag;
}
int n;
int tot;
bool vis[MAXN];
int p[348516], mu[MAXN]; //348513
LL phi[MAXN];
void filter()
{
phi[1] = mu[1] = 1;
for (int i = 2; i < MAXN; ++ i)
{
if (!vis[i]) { mu[i] = -1, phi[i] = i - 1, p[++ tot] = i; }
for (int j = 1; j <= tot && i * p[j] < MAXN; ++ j)
{
vis[i * p[j]] = true;
if (i % p[j] == 0)
{ mu[i * p[j]] = 0, phi[i * p[j]] = phi[i] * p[j]; break; }
else
mu[i * p[j]] = -mu[i], phi[i * p[j]] = phi[i] * phi[p[j]];
}
}
for (int i = 2; i < MAXN; ++ i) mu[i] += mu[i - 1], phi[i] += phi[i - 1];
}
map <LL, PIL> f; //92680
PIL solve(LL x) // Smu[x] = 1 - [2, n]Smu[x / i],
{
if (x < MAXN) return mkpr(mu[x], phi[x]);
if (f.count(x)) return f[x];
int mu = 1; LL phi = x * (x + 1) / 2;
for (LL i = 2, nex = i; i <= x; i = nex + 1)
{
nex = x / (x / i);
PIL val = solve(x / i);
mu -= (nex - i + 1) * val.first;
phi -= (nex - i + 1) * val.second;
}
return f[x] = mkpr(mu, phi);
}
int main()
{
filter();
// printf("%d
", tot);
int Test = in();
while (Test --)
{
n = in();
PIL ans = solve(n);
printf("%lld %d
", ans.second, ans.first);
}
return 0;
}
复杂度
不会证, 据说预处理(n^{frac{2}{3}}), 复杂度为(O(n^{frac{2}{3}}))