gcd之和
求 ∑ i = 1 n gcd ( n , i ) \sum_{i=1}^{n}\gcd(n,i) ∑i=1ngcd(n,i)。
那么我们这一道题讲得详细一点。因为这一道题目的 n ≤ 1 0 9 n \leq 10^9 n≤109。这也就导致了一些算法是过不了的，那么我们就先从最简单的讲起：
对每一项来一遍 gcd \gcd gcd ，然后 gcd \gcd gcd 我们也使用最简单的哪一种去做，也就是从小到大跑，时间复杂度 O ( n 2 ) O(n^2) O(n2)。
#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
int ans=0;
int n=min(a,b);
for(int i=1;i<=n;++i)
{
if(a%i==0&&b%i==0)
{
ans=i;
}
}
return ans;
}
int main()
{
int n;
cin>>n;
int ans=0;
for(int i=1;i<=n;++i)
{
ans+=gcd(n,i);
}
cout<<ans<<endl;
return 0;
}
如果想要快点还可以使用分解质因数，前面讲过了，不说了，那么就可以得到这个式子：
gcd
(
a
,
b
)
=
∏
i
=
1
q
p
1
min
(
x
1
,
y
1
)
×
p
2
min
(
x
2
,
y
2
)
×
⋯
×
p
i
min
(
x
i
,
y
i
)
\gcd(a,b)=\prod_{i=1}^{q} p_1^{\min(x_1,y_1)} \times p_2^{\min(x_2,y_2)} \times \dots \times p_i^{\min(x_i,y_i)}
gcd(a,b)=i=1∏qp1min(x1,y1)×p2min(x2,y2)×⋯×pimin(xi,yi)
那么只要把
gcd
\gcd
gcd 改成这样子就好了：
int gcd(int a,int b)
{
int ans=1;
for(int i=2;i*i<=max(a,b);i++)
{
if(a%i==0||b%i==0)
{
while(a%i==0&&b%i==0)
{
ans*=i;
a/=i;
b/=i;
}
while(a%i==0)
{
a/=i;
}
while(b%i==0)
{
b/=i;
}
}
}
if(a==b)
ans*=a;
return ans;
}
那么因为分解质因数是 O ( n ) O(\sqrt{n}) O(n ) 的时间复杂度，那么这个代码的时间复杂度就是 O ( n n ) O(n \sqrt{n}) O(nn )。
当然了，最经典的求 gcd \gcd gcd 的方法当然是我们的辗转相除法啦，那么代码上面也有，再放一下吧。
int gcd(int a, int b)
{
return b?gcd(b,a%b):a;
}
因为辗转相除法的时间复杂度是 O ( log n ) O(\log n) O(logn)，那么总的时间复杂度就是 O ( n log n ) O(n \log n) O(nlogn) 。显然还是不够的。
我们现在不妨来推测一下，因为
n
≤
2
×
1
0
9
n \leq 2 \times 10^9
n≤2×109 ，所以说连线性的复杂度都吃不消，那么我们只能想到了
l
o
g
log
log 或者是
n
\sqrt{n}
n
。显然
log
\log
log 我也不确定有没有，就算有我也不会，我太弱了qwq。所以我们就要奔着
n
\sqrt n
n
的目标去。我们先来求一下线性的。首先我们要认清楚一件事情，既然是要线性的，那么也就是说我们的枚举目标要改了，如果在去枚举
i
i
i 的话，这样子的话也就是让
gcd
\gcd
gcd 做到
O
(
1
)
O(1)
O(1) 的时间复杂度，那是绝对不可能的吧。也就是我们要把枚举的东西从
i
i
i 换到
gcd
\gcd
gcd 本身上。然后就得到了下面这个式子。
∑
i
=
1
n
gcd
(
i
,
n
)
=
∑
d
∣
n
d
∑
i
=
1
n
d
[
gcd
(
i
d
,
n
)
=
d
]
\sum_{i=1}^n \gcd(i,n) = \sum_{d\mid n}d\sum_{i=1}^{\frac{n}{d}} \left[\gcd(id,n)=d\right]
i=1∑ngcd(i,n)=d∣n∑di=1∑dn[gcd(id,n)=d]
再进行化简（这个方法的数学要求度极高，不过有用）
∑
d
∣
n
d
∑
i
=
1
n
d
[
gcd
(
i
,
n
d
)
=
1
]
=
∑
d
∣
n
d
⋅
φ
(
n
d
)
\sum_{d\mid n} d\sum_{i=1}^{\frac{n}{d}} \left[\gcd\left(i,\frac{n}{d}\right) = 1\right] = \sum_{d\mid n}d\cdot\varphi\left(\frac{n}{d}\right)
d∣n∑di=1∑dn[gcd(i,dn)=1]=d∣n∑d⋅φ(dn)
然后我们就找到了一位好朋友，欧拉函数的影子（是根号做法的关键）。然后上面讲过欧拉函数是一个积性函数，对吧。也就是说
φ
(
a
b
)
=
φ
(
a
)
φ
(
b
)
\varphi(ab) = \varphi(a)\varphi(b)
φ(ab)=φ(a)φ(b) ，不过
a
，
b
a，b
a，b 必须互质，具体的证明可以使用中国剩余定理，不会的同学，翻上面。开始证明：
对于任意正整数使得 x ≤ a ， y ≤ b x \leq a，y \leq b x≤a，y≤b 使得 gcd ( a , x ) = 1 ， gcd ( b , y ) = 1 \gcd(a,x)=1，\gcd(b,y)=1 gcd(a,x)=1，gcd(b,y)=1。
存在一个整数
z
≤
a
b
z \leq ab
z≤ab 使得
gcd
(
z
,
a
b
)
=
1
,
z
≡
x
(
m
o
d
a
)
,
z
≡
y
(
m
o
d
b
)
\gcd(z,ab) = 1, \ z\equiv x\pmod a,\ z\equiv y \pmod b
gcd(z,ab)=1, z≡x(moda), z≡y(modb)
那么我们开始构造，
z
≡
y
a
A
+
x
b
B
(
m
o
d
a
b
)
z\equiv yaA+xbB\pmod {ab}
z≡yaA+xbB(modab)。
其中 a A ≡ 1 ( m o d b ) , b B ≡ 1 ( m o d a ) aA\equiv 1\pmod b,\ \ bB\equiv 1 \pmod a aA≡1(modb), bB≡1(moda)。
那么因为 a ， b a，b a，b 互质，所以肯定存在 A , B A,B A,B。
然后对于任意的正整数 z ≤ z b z \leq zb z≤zb 使得 gcd ( z , a b ) = 1 \gcd(z,ab)=1 gcd(z,ab)=1。
显然的， a a a 和 z z z ， b b b 和 z z z 都是互质的。
也就是说一定存在正整数
x
，
y
x，y
x，y 满足：
gcd
(
a
,
x
)
=
gcd
(
b
,
y
)
=
1
,
z
≡
x
(
m
o
d
a
)
,
z
≡
y
(
m
o
d
b
)
\gcd(a,x) = \gcd(b,y) = 1, \ \ z\equiv x\pmod a,\ \ z\equiv y\pmod b
gcd(a,x)=gcd(b,y)=1, z≡x(moda), z≡y(modb)
所以存在一个从
{
0
<
x
≤
a
∣
gcd
(
a
,
x
)
=
1
}
×
{
0
<
y
≤
b
∣
gcd
(
b
,
y
)
=
1
}
\{0< x\leq a|\gcd(a,x) = 1\}\times \{0< y\leq b|\gcd(b,y)=1\}
{0<x≤a∣gcd(a,x)=1}×{0<y≤b∣gcd(b,y)=1} 到
{
0
<
z
≤
a
b
∣
gcd
(
z
,
a
b
)
=
1
}
\{0< z\leq ab|\gcd(z,ab)=1\}
{0<z≤ab∣gcd(z,ab)=1} 的双射，说明这两个集合的大小相同
所以 φ ( a b ) = φ ( a ) φ ( b ) \varphi(ab) = \varphi(a)\varphi(b) φ(ab)=φ(a)φ(b)。
所以我们可以得到 φ ( p x ) = p x − p x − 1 \varphi(p^x) = p^x - p^{x-1} φ(px)=px−px−1。
所以我们暴力枚举约数：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int phi(int n)
{
int ans=n;
for(inti=2;i*i<=n;++i)
{
if(n%i)
ans=ans/i*(i-1);
while(n%i==0)
n/=i;
}
if(n>1)
ans=ans/n*(n-1);
return ans;
}
signed main()
{
int ans=0;
int n;
cin>>n;
int i=1;
for(;i*i<n;++i)
{
if(n%i==0)
{
ans+=i*phi(n/i)+n/i*phi(i);
}
}
if(i*i==n)
ans+=i*phi(i);
cout<<ans<<endl;
return 0;
}
时间复杂度接近于 O ( n ) O(n) O(n)，那么很明显，还是过不了，怎么办？
接下来的话我们就需要发现~~（bdfs）~~得到一个结果： g ( n ) = ∑ d ∣ n d φ ( n d ) g(n)=\sum_{d|n}d\varphi(\frac{n}{d}) g(n)=∑d∣ndφ(dn)。
证明我也不会，直接求吧：
原式就等于 ∑ d ∣ n ∑ e ∣ m d e ⋅ φ ( m n d e ) = ∑ h ∣ m n h ⋅ φ ( m n h ) = g ( m n ) \sum_{d\mid n}\sum_{e\mid m}de\cdot \varphi(\frac{mn}{de}) = \sum_{h\mid mn} h\cdot \varphi(\frac{mn}h) = g(mn) ∑d∣n∑e∣mde⋅φ(demn)=∑h∣mnh⋅φ(hmn)=g(mn)。
直接将
n
n
n 进行一波因式分解
n
=
∏
i
=
1
q
p
i
a
i
=
p
1
a
1
×
p
2
a
2
×
p
3
a
3
×
⋯
×
p
q
a
q
n = \prod_{i=1}^q p_i^{a_i} = p_1^{a_1}\times p_2^{a_2}\times p_3^{a_3} \times \cdots \times p_q^{a_q}
n=i=1∏qpiai=p1a1×p2a2×p3a3×⋯×pqaq
所以得到了一个式子
g
(
n
)
=
∏
i
=
1
q
g
(
p
i
a
i
)
=
g
(
p
1
a
1
)
×
g
(
p
2
a
2
)
×
g
(
p
3
a
3
)
×
⋯
×
g
(
p
q
a
q
)
g(n) = \prod_{i=1}^q g(p_i^{a_i}) = g(p_1^{a_1})\times g(p_2^{a_2})\times g(p_3^{a_3})\times \cdots\times g(p_q^{a_q})
g(n)=i=1∏qg(piai)=g(p1a1)×g(p2a2)×g(p3a3)×⋯×g(pqaq)
然后我们再考虑：
g
(
p
a
)
=
∑
d
∣
p
a
d
⋅
φ
(
p
a
d
)
=
∑
i
=
0
a
p
i
φ
(
p
a
−
i
)
=
∑
i
=
0
a
−
1
p
i
φ
(
p
a
−
i
)
+
p
a
φ
(
1
)
g(p^a) = \sum_{d\mid p^a}d\cdot \varphi(\frac{p^a}{d}) = \sum_{i=0}^a p^i\varphi(p^{a-i}) = \sum_{i=0}^{a-1}p^i\varphi(p^{a-i})+p^a\varphi(1)
g(pa)=d∣pa∑d⋅φ(dpa)=i=0∑apiφ(pa−i)=i=0∑a−1piφ(pa−i)+paφ(1)
即
g
(
p
a
)
=
p
a
+
∑
i
=
0
a
−
1
p
i
(
p
a
−
i
−
p
a
−
i
−
1
)
=
p
a
+
∑
i
=
0
a
−
1
(
p
a
−
p
a
−
1
)
=
(
a
+
1
)
p
a
−
a
p
a
−
1
g(p^a) = p^a + \sum_{i=0}^{a-1}p^i\left(p^{a-i}-p^{a-i-1}\right) = p^a + \sum_{i=0}^{a-1}\left(p^{a}-p^{a-1}\right) = (a+1)p^a-ap^{a-1}
g(pa)=pa+i=0∑a−1pi(pa−i−pa−i−1)=pa+i=0∑a−1(pa−pa−1)=(a+1)pa−apa−1
至此，我们就可以以优秀的
O
(
n
)
O(\sqrt n)
O(n
) 的时间复杂度解决问题了，完结撒花！！！
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long n;
long long phi=1;
cin>>n;
for(long long i=2;i*i<=n;++i)
{
if(n%i!=0)
continue;
long long p=0,t=1;
while(n%i==0)
{
n=n/i;
p++;
t*=i;
}
phi*=p*(t-t/i)+t;
}
if(n!=1)
phi*=2*n-1;
printf("%lld\n",phi);
return 0;
}