[BZOJ4916]神犇和蒟蒻 杜教筛/Min_25筛

时间:2023-11-11 13:00:20

题目大意:

给定\(n\le 10^9\),求:

1.\(\sum_{i=1}^n\mu(i^2)\)

2.\(\sum_{i=1}^n\varphi(i^2)\)

解释

1.\(\sum_{i=1}^n\mu(i^2)\)

直接输出1

因为对于\(\forall i>1\)有\(\mu (i^2)=0\)

2.\(\sum_{i=1}^n\varphi(i^2)\)

for 杜教筛:

构造函数\(f(i)=\varphi(i^2)\),则有\(f*\mathrm{id}=id^2\),具体推导:

\(\sum_{d|n}\varphi(d^2)\frac n d=\sum_{d|n}d\varphi(d)\frac n d=n\sum_{d|n}d=n^2\)

杜教板子:(风格不太清真,好久以前写的)

#include <bits/stdc++.h>
#define maxn 3000010
#define p 1000000007
#define int long long
using namespace std; map<int, long long> ans_phi;
bool vis[maxn];
int prime[maxn], tot;
long long phi[maxn];
long long inv2, inv6; long long qpow(long long a, long long b)
{
long long res = 1;
while (b > 0)
{
if (b & 1)
res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
} void prework()
{
inv2 = qpow(2, p - 2);
inv6 = qpow(6, p - 2);
phi[1] = 1;
for (int i = 2; i <= 3000000; i++)
{
if (vis[i] == 0)
{
prime[++tot] = i;
phi[i] = i - 1;
}
for (int j = 1; j <= tot && prime[j] * i <= 3000000; j++)
{
vis[i * prime[j]] = 1;
if (i % prime[j] == 0)
{
phi[i * prime[j]] = phi[i] * prime[j] % p;
break;
}
else
phi[i * prime[j]] = phi[i] * (prime[j] - 1) % p;
}
phi[i] = i * phi[i] % p;
(phi[i] += phi[i - 1]) %= p;
}
} long long S_phi(int n)
{
if (n <= 3000000)
return phi[n];
if (ans_phi.count(n))
return ans_phi[n];
long long ans = 1LL * (2 * n + 1) * (n + 1) % p * n % p * inv6 % p;
for (int l = 2, r; l <= n; l = r + 1)
{
r= n / (n / l);
ans = ((ans - (r - l + 1) * (l + r) % p * S_phi(n / l) % p * inv2 % p) % p + p) % p;
}
return ans_phi[n] = ans;
} void read(int &x)
{
static char ch;
x = 0;
ch = getchar();
while (!isdigit(ch))
ch = getchar();
while (isdigit(ch))
{
x = x * 10 + ch - 48;
ch = getchar();
}
} signed main()
{
prework();
// int T;
// read(T);
// for (int n, i = 1; i <= T; i++)
// {
int n;
read(n);
printf("1\n%lld\n", S_phi(n));
// }
return 0;
}

for Min_25筛:

\(f(p)=\varphi(p^2)=p\varphi(p)=p^2-p\)

对于质数我们需要筛一个g2,一个g1,方便判断质数最好再筛一个g0

快速计算\(f(p^k)\)部分也可以参考Sum的Min_25筛写法

这题可以。。。写Min_25筛 后天再写