BZOJ4916: 神犇和蒟蒻(杜教筛)
题意
求
$$\sum_{i = 1}^n \mu(i^2)$$
$$\sum_{i = 1}^n \phi(i^2)$$
$n \leqslant 10^9$
Sol
zz的我看第一问看了10min。
感觉自己智商被侮辱了qwq
基础太垃圾qwq。
算了正经点吧，第一问答案肯定是$1$，还不明白的重学反演吧。
第二位其实也不难
定理：
$\phi(i^2) = i\phi(i)$
$\sum_{d | n} \phi(d) = n$
显然$i$
考虑杜教筛的套路式子
$$g(1)s(n) = \sum_{i = 1}^n g(i)s(\frac{n}{i}) - \sum_{i = 2}^n g(i)s(\frac{n}{i})$$
当我们选择$g(i) = id(i) = i$时卷积的前缀和是比较好算的
$(g * s)(i) = \sum_{i = 1}^n i^2 = \frac{n * (n + 1) * (2n + 1)}{6}$
然后上杜教筛就行了
$$s(n) = \frac{n * (n + 1) * (2n + 1)}{6} - \sum_{i = 2}^n i \phi(\frac{n}{i})$$
人傻自带大常数
#include<cstdio>
#include<map>
#define LL long long
using namespace std;
const int MAXN = 1e7 + 10, mod = 1e9 + 7;
const LL inv = 166666668;
int N, prime[MAXN], vis[MAXN], tot;
LL phi[MAXN];
map<int, LL> ans;
void GetPhi(int N) {
vis[1] = phi[1] = 1;
for(int i = 2; i <= N; i++) {
if(!vis[i]) prime[++tot] = i, phi[i] = i - 1;
for(int j = 1; j <= tot && i * prime[j] <= N; j++) {
vis[i * prime[j]] = 1;
if(!(i % prime[j])) {phi[i * prime[j]] = phi[i] * prime[j]; break;}
phi[i * prime[j]] = phi[i] * phi[prime[j]];
}
}
for(int i = 1; i <= N; i++) phi[i] = (1ll * i * phi[i] % mod + phi[i - 1] % mod) % mod;
}
LL Query(LL x) {
return (x * (x + 1) / 2) % mod;
}
LL S(LL N) {
if(ans[N]) return ans[N];
if(N <= 1e7) return phi[N];
LL sum = N * (N + 1) % mod * (2 * N + 1) % mod * inv % mod, last = 0;
for(int i = 2; i <= N; i = last + 1) {
last = N / (N / i);
sum -= S(N / i) % mod * (Query(last) - Query(i - 1)) % mod;
sum = (sum + mod) % mod;
}
return ans[N] = (sum % mod + mod) % mod;
}
int main() {
GetPhi(1e7);
scanf("%d", &N);
printf("1\n%lld", S(N));
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018-07-19 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录