题目链接 Problem Link

题意：

给定一个正整数 \(N(N\le2^{31}-1)\)

求

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

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

前置芝士

1. \(\mu(p)=-1\) (\(p\)为质数)
2. \(\mu(i*p_j)=\mu(i)*(-1)\) (\(p_j\)为质数且 \(i \ge 1\) 且 \(i \%p_j >0\))
3. \(\mu(i*p_j)=0\) \((p_j\)为质数且 \(i \ge 1\) 且 \(i \%p_j =0\))
4. \(\varphi(p)=p-1\) (\(p\)为质数)
5. \(\varphi(i*p_j)=\varphi(i)*(p_j-1)\) (\(p_j\)为质数且 \(i \ge 1\) 且 \(i \%p_j >0\))
6. \(\varphi(i*p_j)=\varphi(i)*p_j\) \((p_j\)为质数且 \(i \ge 1\) 且 \(i \%p_j =0\))
7. 这两个函数的线性筛法
8. 它们都是积性函数，即 \(\varphi(i)*\varphi(j)=\varphi(i*j) , \mu(i)*\mu(j)=\mu(i*j)\)

先来证两个东西

\((1)\) \(\sum _{d|n}{\varphi(\frac nd)}=n\)

证明：我们要证明的是\(\sum _{d|n}{\varphi(\frac nd)}=n\)， 因为在 \(d|n\) 的条件下 \(\frac nd\) 与 \(d\) 对称，所以原命题变为 \(\sum _{d|n}{\varphi(d)}=n\)

当 \(n=1\) 时，命题显然成立

设 \(p\) 为质数，当 \(n=p\) 时，显然成立，因为 \(\sum_{d|p} \varphi (d)=\varphi(p)+\varphi(1)=p-1+1=p\)

显然对 \(n=p^q\) 也成立，证明：
\[
\sum_{d|p^q} \varphi(d)=\varphi(1)+\varphi(p)+\varphi(p^2)+…+\varphi(p^q)=\sum _{i=0}^{q}{\varphi {(p^i)}}=1+\sum _{i=1}^{q}{\varphi {(p^i)}}
\]
根据 \(\varphi(p^k)=p^k-p^{k-1}=(p-1)*p^{k-1}\) \((p\)为质数\()\)
\[
=1+\sum _{i=1}^{q}{\varphi {(p^i)}}=1+\sum_{i=0}^{q-1}{p^q*(p-1)}
\]
根据等比数列求和公式
\[
=1+(p-1)*\frac {1-p^q}{1-p}=p^q
\]
所以 \(\sum_{d|p^q} \varphi(d)=p^q\) \((p\)为质数\()\)

然后，我们定义函数 ，\(F(n)=\sum_{d|n}\varphi(d)\)，也就是说 \(F(p^k)=\sum _{d|p^k}\varphi (d)\)，\(F(p^k)\) 显然为积性函数，\(p\) 为质数

证明：
\[
F(p_1^n)*F(p_2^m)=\sum_{i|p_1^n}\varphi(i)*\sum_{j|p_2^m}\varphi(j)=\sum_{i|p_1^n}\sum_{j|p_2^m}\varphi(i)*\varphi(j)
\]
我们假设 \(p_1\) 不等于 \(p_2\) ，那么因为 \(gcd(p_1,p_2)=1\)，所以 \(gcd(p_1^a,p_2^a)=1\)

于是在上面的柿子中，\(gcd(i,j)=1\)，所以 \(\varphi(i)*\varphi(j)=\varphi(i*j)\)

所以
\[
F(p_1^n)*F(p_2^m)=\sum_{i|p_1^n}\sum_{j|p_2^m}\varphi(i*j)=\sum_{d|p_1^n*p_2^m}\varphi(d)=F(p_1^n*p_2^m)
\]
然后，因为整数唯一分解定理，一个正整数可以被分解为 \(p_1^{b_1}*p_2^{b_2}*…*p_k^{b_k}\) 的形式，\(p\) 为质数，那么
\[
F(n)=F(p_1^{b_1}*p_2^{b_2}*…*p_k^{b_k})=F(p_1^{b_1})*F(p_2^{b_2})*…*F(p_k^{b_k})=p_1^{b_1}*p_2^{b_2}*…*p_k^{b_k}=n
\]
所以
\[
\sum_{d|n}\varphi(d)=n
\]
因为， \(n\)为任何正整数时都成立，所以原命题成立

\((2)\) \(\sum _{d|n} \mu(d) = \left\{\begin{aligned} 1 & (n=1)\\ 0 & (n\ne1) \end{aligned}\right.\)

设 \(n=p_1^{b_1}*p_2^{b_2}* … * p_k^{b_k} , m=p_1*p_2* … *p_k\)
\[
\sum_{d|n}\mu(d)=\sum_{i=1}^{b_1}\mu(p_1i)+\sum_{i=1}^{b_2}\mu(p_2^i)+…\sum_{i=1}^{b_k}\mu(p_k^i)
\]

\[
=\mu(p_1)+\mu(p_2)+…+\mu(p_k)+\sum_{i=2}^{b_1}\mu(p_1i)+\sum_{i=2}^{b_2}\mu(p_2^i)+…\sum_{i=2}^{b_k}\mu(p_k^i)
\]

\[
=m+0+0+…+0=m=\sum_{d|m}{\mu(d)}
\]

然后你就看每一个项有多少个质数乘起来，由于质数互不相同，

所以可以套用二项式定理和前置芝士第二条来做
\[
\sum_{d|n}\mu(d)=\sum_{d|m}{\mu(d)}=\sum_{i=0}^kC^i_k*(-1)^i=(1+(-1))^k
\]
当 \(k>0\) 的时候显然为 \(0\) ，证明了 $\sum _{d|n}\mu(d)=0 $ \((n \ne 1)\)

当 \(k=0\) 的时候，\(n\) 就为 \(1\) ，直接代入 \(\sum_{d|n}\mu(d)\) 就可知答案为 \(1\) ，证明了 $\sum _{d|n}\mu(d)=1 $ \((n = 1)\)

于是原命题成立

好，证明正式开始

先说一个叫做狄利克雷卷积的东西

我们定义函数 \(f\) , \(g\) 的狄利克雷卷积为 \((f*g)(i)\)

\((f*g)(i)=\sum_{d|i}f(d)*g(\frac id)\)

我们设 \(S(n)=\sum _{i=1}^n{f(i)}\)，也就是函数的前缀和
\[
\sum_{i=1}^{n}(g*f)(i)=\sum_{i=1}^n(\sum_{d|i}{g(d)*f(\frac id)} )
\]

然后跟 #1 的 \(60\) 分做法类似，把它变一变，变成枚举约数 \(d\)
\[
=\sum_{d=1}^n(g(d)*\sum_{i=1}^{\lfloor \frac nd \rfloor}{f(i)} )
\]
用 \(S(i)\) 替换后面那个 \(\sum\)
\[
=\sum_{d=1}^ng(d)*S(\lfloor \frac nd \rfloor)
\]
然后我们要用移项大法：

\[
0=\sum_{i=1}^{n}(g*f)(i)-\sum_{i=1}^{n}(g*f)(i)
\]

\[
0=\sum_{i=1}^{n}(g*f)(i)-\sum_{d=1}^ng(d)*S(\lfloor \frac nd \rfloor)
\]

\[
0=\sum_{i=1}^{n}(g*f)(i)-\sum_{d=2}^ng(d)*S(\lfloor \frac nd \rfloor)-g(1)*S(n)
\]

\[
g(1)*S(n)=\sum_{i=1}^{n}(g*f)(i)-\sum_{d=2}^ng(d)*S(\lfloor \frac nd \rfloor)
\]

此时，\(S(n)\) 就出现了

然后我们代入欧拉函数，

设 \(f(i)=\varphi(i) , g(i)=1\)
\[
\sum_{i=1}^n\varphi(i)=1*S(n)=\sum_{i=1}^{n}(g*f)(i)-\sum_{d=2}^n 1*S(\lfloor \frac nd \rfloor)
\]
我们再来看一下狄利克雷卷积的定义：
\[
\sum_{i=1}^{n}(g*f)(i)=\sum_{i=1}^n(\sum_{d|i}{g(d)*f(\frac id)} )
\]

\[
=\sum_{i=1}^n(\sum_{d|i}f(\frac id) )
\]

我们知道 \(\sum _{d|i}{\varphi(\frac id)}=i\)

所以
\[
\sum_{i=1}^{n}(g*f)(i)=\sum_{i=1}^ni= \frac {n*(n+1)}{2}
\]
把这个结果回代上面的柿子

\[
g(1)*S(n)= \frac {n*(n+1)}{2}-\sum_{d=2}^n g(d)*S(\lfloor \frac nd \rfloor)
\]

\[
S(n)= \frac {n*(n+1)}{2}-\sum_{d=2}^n S(\lfloor \frac nd \rfloor)
\]

好，这个可以递归求了，其中，后面那个 \(\sum\) 可以 \(O(\sqrt {n})\) 来求

我们先来运行一下这段代码

int n=30;
for(int d=1;d<=n;++d)
    printf("%d ",n/d*d);

输出结果为：

30 15 10 7 6 5 4 3 3 3 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

观察一下会发现相同的数很多，而且都堆在一起

这里有个性质，以 \(l\) 为左端点的相同的数的区间的右端点是 \(\lfloor \frac n{\lfloor \frac nl \rfloor} \rfloor\)

证明：

对于任意一个 \(l(l\le n)\)，我们需要找到一个最大的 \(r(l \le r \le n)\)，使得 \(\lfloor \frac nl \rfloor=\lfloor \frac nr \rfloor\).
\[
\lfloor \frac nl \rfloor \le \frac nl
\]

\[
\lfloor \frac n{\lfloor \frac nl \rfloor} \rfloor \ge \lfloor \frac n{\frac nl} \rfloor=\lfloor l \rfloor=l
\]

\[
l \le \lfloor \frac n{\lfloor \frac nl \rfloor} \rfloor
\]

所以 \(r=\lfloor \frac n{\lfloor \frac nl \rfloor} \rfloor\)

代码大约就是

for(int l=1,r;l<=n;l=r+1)
{
    r=n/(n/l);
    reg int now=n/l; // 区间内的数的值
   // do something ...
}

这个复杂度姑且可以认为是 \(O(\sqrt n)\) 的

那么对于欧拉函数，在 \([l,r]\) 中的答案就是

\[
(r-l+1)*S(\lfloor\frac nl \rfloor)
\]

把这堆 \(l,r\) 的答案加起来，再用 \(\frac {n*(n+1)}{2}\) 减去后就是 \(S(n)\)了

先线性筛预处理出 \(S(1\) ~ \(1000000)\)，然后记忆化搜索，开个 \(map\) 或者蛤希存 \(S(i)\) 的结果，当然如果 \(i \le 1000000\) 就直接查表

莫比乌斯函数也差不多，这里 \(S(n)=\sum_{i=1}^n\mu(i)\)

用狄利克雷卷积

设 \(f(i)=\mu(i) , g(i)=1\)，那么
\[
\sum_{i=1}^n{(g*f)(i)}=\sum_{i=1}^n\sum_{d|i}g(d)*f(\frac id)
\]

\[
=\sum_{i=1}^n\sum_{d|i}\mu(\frac id)=\sum_{i=1}^n\sum_{d|i}\mu(d)=1+\sum_{i=2}^n0=1
\]

我们已经知道，

\[
g(1)*S(n)=\sum_{i=1}^{n}(g*f)(i)-\sum_{d=2}^ng(d)*S(\lfloor \frac nd \rfloor)
\]
于是使用传统艺能，代入
\[
S(n)=1-\sum_{d=2}^ng(d)*S(\lfloor \frac nd \rfloor)
\]

\[
S(n)=1-\sum_{d=2}^S(\lfloor \frac nd \rfloor)
\]

然后就可以和欧拉函数那个一样递归搞了

复杂度大约为 \(O(n^{\frac 23})\)

// This code wrote by chtholly_micromaker(MicroMaker)
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define reg register
#define int long long
using namespace std;
const int MaxN=3000050;
template <class t> inline void read(t &s)
{
    s=0;
    reg int f=1;
    reg char c=getchar();
    while(!isdigit(c))
    {
        if(c=='-')
            f=-1;
        c=getchar();
    }
    while(isdigit(c))
        s=(s<<3)+(s<<1)+(c^48),c=getchar();
    s*=f;
    return;
}
// bitset<MaxN> isp;
bool isp[MaxN];
int pr[MaxN],prn;
int phi[MaxN],mu[MaxN];
map<int,int> dp;
inline void Init(int n)
{
    phi[1]=mu[1]=1;
    for(int i=2;i<=n;++i)
    {
        // if(!isp.test(i))
        if(!isp[i])
        {
            pr[++prn]=i;
            phi[i]=i-1;
            mu[i]=-1;
        }
        for(int j=1;j<=prn&&i*pr[j]<=n;++j)
        {
            // isp.set(i*pr[j],1);
            reg int t=i*pr[j];
            isp[t]=true;
            if(i%pr[j])
            {
                phi[t]=phi[i]*(pr[j]-1);
                mu[t]=mu[i]*(-1);
            }
            else
            {
                phi[t]=phi[i]*pr[j];
                mu[t]=0;
                break;
            }
        }
    }
    for(int i=1;i<=n;++i)
        phi[i]+=phi[i-1],mu[i]+=mu[i-1];
    return;
}
inline int calcphi(int n)
{
    if(n<=3000000)
        return phi[n];
    if(dp.find(n)!=dp.end())
        return dp[n];
    reg int ans=0;
    for(reg int l=2,r;l<=n;l=r+1)
    {
        r=n/(n/l);
        ans+=(r-l+1)*calcphi(n/l);
    }
    ans=n*(n+1)/2-ans;
    dp[n]=ans;
    return ans;
}
inline int calcmu(int n)
{
    if(n<=3000000)
        return mu[n];
    if(dp.find(n)!=dp.end())
        return dp[n];
    reg int ans=0;
    for(reg int l=2,r;l<=n;l=r+1)
    {
        r=n/(n/l);
        ans+=(r-l+1)*calcmu(n/l);
    }
    dp[n]=1-ans;
    return 1-ans;
}
inline void work()
{
    int n;cin>>n;
    dp.clear();
    reg int ansphi=calcphi(n);
    dp.clear();
    reg int ansmu=calcmu(n);
    printf("%lld %lld\n",ansphi,ansmu);
    return;
}
signed main(void)
{
    Init(3000000);
    int t;cin>>t;
    while(t--)
        work();
    return 0;
}

如果 \(TLE\) 的话注意常数优化或者开启 \(Ofast\)

或者线筛筛到 \(3000000\) 也可以过