题目传送门
>原文链接<

题解 :

杜教筛模版

  • 首先看ans1

    要求的就是 \sum\limits_{i=1}^{n}\varphi(i)

    引入性质1 :\sum\limits_{d|n}\varphi(d) = n

    \to \sum\limits_{i=1}^{n}\sum\limits_{d|i}\varphi(d) = \sum\limits_{i=1}^{n}i = \frac{n(n+1)}{2}

    其实 \sum\limits_{d|i}\varphi(d)就相当于对1, 2, 3,\cdots, n 所有数的每个约数求一个S_{\varphi}

    我们不枚举1, 2, 3,\cdots,n的所有约数,而是换一个有助于下一步计算的来枚举

    \sum\limits_{d=1}^{\lfloor\frac{n}{i}\rfloor}\varphi(d)i枚举到n的意义下恰好等同于\sum\limits_{d|i}\varphi(d)

    你可以发现每个这样枚举的d都恰好对应了一个之前要枚举约数的数i

    这步稍微有点难,如果没能很好的理解,请从枚举总量不变,枚举的数的性质也都是约数这方面去考虑。

    我们回到原来的式子,你发现已经变成了\sum\limits_{i=1}^{n}\sum\limits_{d=1}^{\lfloor\frac{n}{i}\rfloor}\varphi(d) = \frac{n(n+1)}{2}

    \sum\limits_{d=1}^{\lfloor\frac{n}{i}\rfloor}\varphi(d)其实就是我们要求的S_{\varphi}

    \to \sum\limits_{i=1}^nS(\lfloor\frac{n}{i}\rfloor) = \frac{n(n+1)}{2}

    我们把枚举的i=1单独拿出来,就变成了S(n)=\frac{n(n+1)}{2}-\sum\limits_{i=2}^{n}S(\lfloor\frac{n}{i}\rfloor)

    \sum\limits_{i=2}^{n}S(\lfloor\frac{n}{i}\rfloor)由于\lfloor\frac{n}{i}\rfloor只有\sqrt n种取值,递归这些取值求解即可。

    由于会有很多重复的计算,所以要用map记忆化搜索。

    另外,这样的复杂度是\Theta(N^{\frac{3}{4}})的,通过预处理前N^{\frac{2}{3}}S(n)可以使复杂度降到\Theta(N^{\frac{2}{3}}),一次线筛即可。

    ans2的推导方式几乎和S_\varphi一样,只需要引入性质2:\sum\limits_{d|n}\mu(d)=1替换性质1即可,枚举过程不变。

代码 :

#include <map>#include <cstdio>#include <iostream>#define ll long longusing namespace std;const int N = 5000000;map<int, pair<ll, int> >f;bool vis[N];int pr[N], mu[N], s2[N], tot;int phi[N];ll s1[N];void query(ll n, ll &a1, ll &a2) { if(n < N) return a1 = s1[n], a2 = s2[n], void(); if(f.find(n) != f.end()) return a1 = f[n].first, a2 = f[n].second, void(); a1 = n*(n+1)/2, a2 = 1; long long i, lst, tmp1, tmp2; for(i = 2; i <= n; i = lst+1) { lst = n/(n/i), query(n/i, tmp1, tmp2); a1 -= (lst-i+1)*tmp1; a2 -= (lst-i+1)*tmp2; } f[n] = make_pair(a1, a2);}void init() { mu[1] = phi[1] = s1[1] = s2[1] = 1; for(int i = 2; i < N; i ++ ) { if(!vis[i]) { pr[++tot] = i; phi[i] = i-1; mu[i] = -1; } for(int j = 1; j <= tot && i*pr[j] < N; j ++ ) { vis[i*pr[j]] = 1; if(!(i%pr[j])) { phi[i*pr[j]] = phi[i]*pr[j]; break; } phi[i*pr[j]] = phi[i]*(pr[j]-1); mu[i*pr[j]] = -mu[i]; } s1[i] = s1[i-1]+phi[i]; s2[i] = s2[i-1]+mu[i]; }}int main() { init(); ll n; scanf("%lld", &n); ll ans1, ans2; ans1 = ans2 = 0; query(n, ans1, ans2); printf("%lld\n", ans1);}