杜教筛的作用为计算积性函数前缀和
即求$sum_{i=1}^n f(i)$ f(i)为积性函数
构造：$h = f * g$
即:$S(n)=sum_{i=1}^nf(i)$
求$sum_{i=1}^nh(i)$
开始推式子：
$sum{i=1}^nh(i)=sum{i=1}^nsum_{d|i}g(d) * f(n/d)$
$=sum{d=1}^ng(d)sum{i=1}^{n/d}f(i)$
即：
$sum{i=1}^nh(i)=sum{d=1}^ng(d)*S(n/d)$
即：
$sum{i=1}^nh(i)=g(1)S(n)+sum{i=2}^ng(d)S(n/d)$
$g(1)*S(n)=sum{i=1}^n-sum{d=2}^ng(d)S(n/d)$
其中：
$h(i)=(f*g)(i)$
杜教筛应用：
1.求$S(n)=sum_{i=1}^nφ(i)$
因为：$φ * I = id$
代入可得:
$S(n)=sum{i=1}^n i - sum{d=2}^nS(n/d)$
2.求$S(n)=sum_{i=1}^nu(i)$
因为$u * I = e$
易得:
$S(n) = 1 - sum_{i=1}^nS(n/d)$
3.求$S(n)=sum_{i=1}^ni*φ(i)$
首先
狄利克雷卷积：
$sum_{d|n}(d φ(n)) g(n/d)$;
令g配成id:
$sum_{d|n}(d φ(d)) g(n/d)$
即:
$sum{d|n}(dφ(d) n / d=sum{d|n}n * φ(d)=n^2$
即：
$S(n)=sum{i=1}^ni^2 - sum{d=2}^n d * S(n/d)$
附上洛谷模板题代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
|
#define LL long long
using namespace std;
inline int ()
{
int X = 0,w = 0;char ch = 0;
while(!isdigit(ch)){w |= ch == '-';ch = getchar();}
while(isdigit(ch)){X = (X << 3) + (X << 1) + ch - '0';ch = getchar();}
return w ? -X:X;
}
const int N = 5e6 + 501;
int u[N];
LL phi[N], s1[N];
int prime[N], tot;
bool flag[N];
int s2[N], n;
map<LL,LL>w1;
map<int,int>w;
void get_prime(int n)
{
flag[1] = 1;
u[1] = 1;
phi[1] = 1;
for(int i = 2;i <= n;i ++)
{
if(!flag[i])prime[++ tot] = i,u[i] = -1,phi[i] = i - 1;
for(int j = 1;j <= tot && i * prime[j] <= n;j ++)
{
flag[i * prime[j]] = 1;
if(i % prime[j] == 0)
{
u[i * prime[j]] = 0;
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
u[i * prime[j]] = -u[i];
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
}
for(int i = 1;i <= n;i ++)
s1[i] = s1[i - 1] + phi[i],s2[i] = s2[i - 1] + u[i];
}
int get_mu(int x)
{
if(x <= 5000000)return s2[x];
if(w[x])return w[x];
int ans = 1;
for(int l = 2,r;l <= x;l = r + 1)
{
r = x / (x / l);
ans -= (r - l + 1) * get_mu(x / l);
}
return w[x] = ans;
}
LL get_phi(LL x)
{
if(x <= 5000000)return s1[x];
if(w1[x])return w1[x];
LL ans = x * (x + 1) / 2;
for(LL l = 2,r;l <= x;l = r + 1)
{
r = x / (x / l);
ans -= (r - l + 1) * get_phi(x / l);
}
return w1[x] = ans;
}
signed main()
{
int t = read();
get_prime(5000000);
for(int i = 1;i <= t;i ++)
{
int x = read();
printf("%lld %dn",get_phi(x),get_mu(x));
}
}
|
近期评论