题解 P2303 【[SDOi2012]Longge的问题】

· · 题解

洛谷的markdown为啥不支持多行公式啊啊啊

想要公式好看点还是去博客看吧 传送门，里面也多写了一些有关本题的拓展...

bux fixed：

修了下无法正常显示的公式

 

题目传送门：https://www.luogu.org/problem/P2303

给定一个整数n，求

\sum_{i=1}^n \gcd(n,i)

蒟蒻随便yy了一下搞出来个O(\sqrt{n})的算法 这题数据怎么这么水

首先看到gcd我们就下意识的对它反演一波对吧

第一步

\sum_{i=1}^n \gcd(n,i) = \sum_{d|n} \varphi(d) \frac{n}{d}

这里提供两种化法，得到的结果都是这个。

法一

根据欧拉函数和式

n = \sum_{d|n} \varphi(d)

暴力推导即可

\sum_{i=1}^n \gcd(n,i) = \sum_{i=1}^n \sum_{d|\gcd(n,i)} \varphi(d) = \sum_{d|n} \sum_{i=1}^{\frac n d} \varphi(d) = \sum_{d|n} \varphi(d) \frac n d

法二

根据欧拉函数的定义式

\varphi(n) = \sum_{i=1}^n [\gcd(n,i) = 1]

PS：\varphi(n)表示1~n-1内与n互质的数，将和式上界提升到n不但不会影响正确性（\gcd(n,n) = n \neq 1），而且让\varphi(1)不用特判。

易得

\sum_{i=1}^n \gcd(n,i) = \sum_{d|n} d \sum_{i=1}^n [\gcd(n,i) = d] = \sum_{d|n} d \sum_{i=1}^{\frac n d} [\gcd(\frac n d,i) = 1] = \sum_{d|n} d \varphi(\frac n d) = \sum_{d|n} \varphi(d) \frac n d

这一步还是比较简单的。稍有基础的同学大概都会吧

第二步

令

g(n) = \sum_{i=1}^n \gcd(n,i) = \sum_{d|n} \varphi(d) \frac{n}{d}

我们希望求g的在n的函数值。容易发现右式是狄利克雷卷积\varphi * Id，也就是说g也是积性函数。所以考虑质因数分解n，最后用积性累乘出来

即

g(n) = g({p_1}^{c_1}) g({p_2}^{c_2}) ... g({p_n}^{c_n})

则只需求g(p^c)（这里省略下标）

p^c$的因数分别为$1$，$p$，$p^2$，...，$ p^c

所以有

g(p^c) = \sum_{i=0}^{c} \varphi(p^i) \frac{p^c}{p^i} = \sum_{i=0}^{c} \varphi(p^i) p^{c-i}

求\varphi(p^c)

考虑先弄出上式中\varphi(p^i)的封闭形式，再带回原式看看

根据欧拉函数通式

\varphi(n) = n \prod_{i=1}^k (1 - \frac 1 {p_i})

（这个\pi指的是分解质因数）

易得

\varphi(p^c) = p^c (1 - p) = p^c - p^{c-1}

注意这个式子需要在c=0时特判，因为\varphi(1) = 1（1可以视作分解不出任何质因数）

求g(p^c)

得到了\varphi(p^c)，带回之前未推完的g(p^c)的式子，得

g(p^c) = \sum_{i=0}^{c} \varphi(p^i) p^{c-i} = p^c + \sum_{i=1}^{c} (p^i - p^{i-1}) p^{c-i} = p^c + \sum_{i=1}^{c} (p^c - p^{c-1}) = p^c + c (p^c - p^{c-1}) = (c+1)p^c - c \ p^{c-1}

（中途对i=0进行了特殊讨论）（该式同样不适用于c=0的情况）

然后积性合并起来就完了

冷静分析一波时间复杂度。质因数分解消耗O(\sqrt n)的时间复杂度，分解出不超过O(log_2 n)个p^c，每个g(p^c)的计算是O(1)的。所以总时间复杂度为O(\sqrt n)

代码

非常简单的代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long ll;

ll p[1005],c[1005],g[1005];ll kN;
void Div(ll n){
    kN=0;
    for(ll i=2;i*i<=n;i++){
        if(n%i==0){
            kN++;p[kN]=i;
            g[kN]=1;
            ll e=0;while(n%i==0) e++,n/=i,g[kN]*=i;
            c[kN]=e;
        }
    }
    if(n!=1) kN++,p[kN]=n,c[kN]=1,g[kN]=n;
}
ll N;
int main(){
    cin>>N;
    Div(N);
    ll pdt=1;
    for(int i=1;i<=kN;i++) pdt=pdt*((c[i]+1)*g[i]-c[i]*g[i]/p[i]);
    cout<<pdt;
    return 0;
}

这式子长得跟小粉兔菊苣的题解很像？