同见于我的洛谷博客

---

Update

阅读本篇前,请先阅读 OI wiki 相关章目

因为笔者 $\LaTeX$ 欠佳,若炸了可到博客上去看

Part 0: 一些记号&约定

• $P$ : 质数集
• $\operatorname M$ : 这是一个我定义的数论函数,以下会讲到
• $*$ : 狄卷

Part 1: 转化问题

为方便讨论,设 $\operatorname M(x)=\sum\limits^x_{i=1}\gcd\{i,x\}$

那么问题就转化成了对 $\operatorname M$ 的性质进行研究,从而快速计算出 $\operatorname M(x)$ !

Part 2: 一些引理

考虑到 $\gcd$ 的特性,易有:

$$\operatorname M(x)=\sum\limits^x_{i=1}\gcd\{i,x\}\\=\sum\limits_{d\mid x}d\sum\limits^x_{i=1}[\gcd\{i,x\}=d]\\=\sum\limits_{d\mid x}d\sum\limits^{\frac xd}_{i=1}[\gcd\{i,\frac xd\}=1]\\=\sum\limits_{d\mid x}d\varphi(\frac xd)=(\operatorname{id}* \varphi)(x) $$

即:

$$\operatorname M=\operatorname{id}* \varphi$$

$\because\operatorname{id},\varphi$ 均积性函数 $\\\therefore\operatorname M$为积性函数

这就意味着,若对 $x$ 进行质因数分解,则:

$$\operatorname M(\prod\limits^k_{i=1}p_i^{n_i})=\prod\limits^k_{i=1}\operatorname M(p_i^{n_i})\ \ \ \ (p_i\in P,n_i \in N^+) $$

故倘能快速计算 $\operatorname M(p^n)$,则可以 $O(\sqrt x)$ 计算原式值!$\ \ \ \ (p\in P,n\in N^+)$

但如何快速计算 $\operatorname M(p^n)$ 呢?

显然,

$$\operatorname M(p^n)=\sum\limits^n_{i=0}p^{n-i}\times\varphi(p^i)\\=p^n+\sum\limits^n_{i=1}p^{n-i}\times\varphi(p^i)\\=p^n+\sum\limits^n_{i=1}p^{n-i}\times((p-1)\times p^{i-1})\\=p^n+\sum\limits^n_{i=1}p^{n-1}\times(p-1)\\=p^n+n\times p^{n-1}\times(p-1)\\=(n+1)p^n-np^{n-1} $$

于是可以在对 $x$ 除尽 $p$ 的同时统计 $n$ 与 $p^n$ ,总复杂度为 $O(\sqrt x)$

Part 3: 核心代码示范 (C++)

知道你们就想要这个

mod 表示模数,为 $0$ 时不取模

AC记录

typedef T unsigned long long;
inline T M(T num,T mod)
{
    T ans=1,k,q;
    for(T i=2;i*i<=num;i++)
        if(!(num%i))
        {
            k=1,q=i,num/=i;
            while(!(num%i))k++,q*=i,num/=i;
            ans*=(k+1)*q-k*(q/i);
            if(mod)ans%=mod;
        }
    if(num^1)
        ans*=(num<<1)-1,ans=mod?(ans%mod):ans;
    return ans;
}

END

谢谢观赏!