题目大意:
给定\(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筛 后天再写