莫比乌斯反演 引入 莫比乌斯反演是数论中的重要内容。对于一些函数 𝑓 ( 𝑛 ) f ( n ) ,如果很难直接求出它的值,而容易求出其倍数和或约数和 𝑔 ( 𝑛 ) g ( n ) ,那么可以通过莫比乌斯反演简化运算,求得 𝑓 ( 𝑛 ) f ( n ) 的值。
开始学习莫比乌斯反演前,需要先学习一些前置知识:数论分块 、狄利克雷卷积 。
莫比乌斯函数 定义 𝜇 μ 为莫比乌斯函数,定义为
𝜇 ( 𝑛 ) = ⎧ { { ⎨ { { ⎩ 1 𝑛 = 1 0 𝑛 含有平方因子 ( − 1 ) 𝑘 𝑘 为 𝑛 的本质不同质因子个数 μ ( n ) = { 1 n = 1 0 n 含有平方因子 ( − 1 ) k k 为 n 的本质不同质因子个数 详细解释一下:
令 𝑛 = ∏ 𝑘 𝑖 = 1 𝑝 𝑐 𝑖 𝑖 n = ∏ i = 1 k p i c i ,其中 𝑝 𝑖 p i 为质因子,𝑐 𝑖 ≥ 1 c i ≥ 1 。上述定义表示:
𝑛 = 1 n = 1 时,𝜇 ( 𝑛 ) = 1 μ ( n ) = 1 ;对于 𝑛 ≠ 1 n ≠ 1 时:当存在 𝑖 ∈ [ 1 , 𝑘 ] i ∈ [ 1 , k ] ,使得 𝑐 𝑖 > 1 c i > 1 时,𝜇 ( 𝑛 ) = 0 μ ( n ) = 0 ,也就是说只要某个质因子出现的次数超过一次,𝜇 ( 𝑛 ) μ ( n ) 就等于 0 0 ; 当任意 𝑖 ∈ [ 1 , 𝑘 ] i ∈ [ 1 , k ] ,都有 𝑐 𝑖 = 1 c i = 1 时,𝜇 ( 𝑛 ) = ( − 1 ) 𝑘 μ ( n ) = ( − 1 ) k ,也就是说每个质因子都仅仅只出现过一次时,即 𝑛 = ∏ 𝑘 𝑖 = 1 𝑝 𝑖 n = ∏ i = 1 k p i ,{ 𝑝 𝑖 } 𝑘 𝑖 = 1 { p i } i = 1 k 中个元素唯一时,𝜇 ( 𝑛 ) μ ( n ) 等于 − 1 − 1 的 𝑘 k 次幂,此处 𝑘 k 指的便是仅仅只出现过一次的质因子的总个数。 性质 莫比乌斯函数不仅是积性函数,还有如下性质:
∑ 𝑑 ∣ 𝑛 𝜇 ( 𝑑 ) = { 1 𝑛 = 1 0 𝑛 ≠ 1 ∑ d ∣ n μ ( d ) = { 1 n = 1 0 n ≠ 1 即 ∑ 𝑑 ∣ 𝑛 𝜇 ( 𝑑 ) = 𝜀 ( 𝑛 ) ∑ d ∣ n μ ( d ) = ε ( n ) ,𝜇 ∗ 1 = 𝜀 μ ∗ 1 = ε
证明 设 𝑛 = 𝑘 ∏ 𝑖 = 1 𝑝 𝑖 𝑐 𝑖 , 𝑛 ′ = 𝑘 ∏ 𝑖 = 1 𝑝 𝑖 n = ∏ i = 1 k p i c i , n ′ = ∏ i = 1 k p i
那么 ∑ 𝑑 ∣ 𝑛 𝜇 ( 𝑑 ) = ∑ 𝑑 ∣ 𝑛 ′ 𝜇 ( 𝑑 ) = 𝑘 ∑ 𝑖 = 0 ( 𝑘 𝑖 ) ⋅ ( − 1 ) 𝑖 = ( 1 + ( − 1 ) ) 𝑘 ∑ d ∣ n μ ( d ) = ∑ d ∣ n ′ μ ( d ) = ∑ i = 0 k ( k i ) ⋅ ( − 1 ) i = ( 1 + ( − 1 ) ) k
根据二项式定理,易知该式子的值在 𝑘 = 0 k = 0 即 𝑛 = 1 n = 1 时值为 1 1 否则为 0 0 ,这也同时证明了 ∑ 𝑑 ∣ 𝑛 𝜇 ( 𝑑 ) = [ 𝑛 = 1 ] = 𝜀 ( 𝑛 ) ∑ d ∣ n μ ( d ) = [ n = 1 ] = ε ( n ) 以及 𝜇 ∗ 1 = 𝜀 μ ∗ 1 = ε
注 这个性质意味着,莫比乌斯函数在狄利克雷生成函数中,等价于黎曼函数 𝜁 ζ 的倒数。所以在狄利克雷卷积中,莫比乌斯函数是常数函数 1 1 的逆元。
补充结论 反演结论:[ g c d ( 𝑖 , 𝑗 ) = 1 ] = ∑ 𝑑 ∣ g c d ( 𝑖 , 𝑗 ) 𝜇 ( 𝑑 ) [ gcd ( i , j ) = 1 ] = ∑ d ∣ gcd ( i , j ) μ ( d )
直接推导 :如果看懂了上一个结论,这个结论稍加思考便可以推出:如果 g c d ( 𝑖 , 𝑗 ) = 1 gcd ( i , j ) = 1 的话,那么代表着我们按上个结论中枚举的那个 𝑛 n 是 1 1 ,也就是式子的值是 1 1 ,反之,有一个与 [ g c d ( 𝑖 , 𝑗 ) = 1 ] [ gcd ( i , j ) = 1 ] 相同的值:0 0
利用 𝜀 ε 函数 :根据上一结论,[ g c d ( 𝑖 , 𝑗 ) = 1 ] = 𝜀 ( g c d ( 𝑖 , 𝑗 ) ) [ gcd ( i , j ) = 1 ] = ε ( gcd ( i , j ) ) ,将 𝜀 ε 展开即可。
线性筛 由于 𝜇 μ 函数为积性函数,因此可以线性筛莫比乌斯函数(线性筛基本可以求所有的积性函数,尽管方法不尽相同)。
线性筛实现 拓展 证明
𝜑 ∗ 1 = i d φ ∗ 1 = id 将 𝑛 n 分解质因数:𝑛 = 𝑘 ∏ 𝑖 = 1 𝑝 𝑖 𝑐 𝑖 n = ∏ i = 1 k p i c i
首先,因为 𝜑 φ 是积性函数,故只要证明当 𝑛 ′ = 𝑝 𝑐 n ′ = p c 时 𝜑 ∗ 1 = ∑ 𝑑 ∣ 𝑛 ′ 𝜑 ( 𝑛 ′ 𝑑 ) = i d φ ∗ 1 = ∑ d ∣ n ′ φ ( n ′ d ) = id 成立即可。
因为 𝑝 p 是质数,于是 𝑑 = 𝑝 0 , 𝑝 1 , 𝑝 2 , ⋯ , 𝑝 𝑐 d = p 0 , p 1 , p 2 , ⋯ , p c
易知如下过程:
𝜑 ∗ 1 = ∑ 𝑑 ∣ 𝑛 𝜑 ( 𝑛 𝑑 ) = 𝑐 ∑ 𝑖 = 0 𝜑 ( 𝑝 𝑖 ) = 1 + 𝑝 0 ⋅ ( 𝑝 − 1 ) + 𝑝 1 ⋅ ( 𝑝 − 1 ) + ⋯ + 𝑝 𝑐 − 1 ⋅ ( 𝑝 − 1 ) = 𝑝 𝑐 = i d φ ∗ 1 = ∑ d ∣ n φ ( n d ) = ∑ i = 0 c φ ( p i ) = 1 + p 0 ⋅ ( p − 1 ) + p 1 ⋅ ( p − 1 ) + ⋯ + p c − 1 ⋅ ( p − 1 ) = p c = id 该式子两侧同时卷 𝜇 μ 可得 𝜑 ( 𝑛 ) = ∑ 𝑑 ∣ 𝑛 𝑑 ⋅ 𝜇 ( 𝑛 𝑑 ) φ ( n ) = ∑ d ∣ n d ⋅ μ ( n d )
莫比乌斯变换 设 𝑓 ( 𝑛 ) , 𝑔 ( 𝑛 ) f ( n ) , g ( n ) 为两个数论函数。
形式一:如果有 𝑓 ( 𝑛 ) = ∑ 𝑑 ∣ 𝑛 𝑔 ( 𝑑 ) f ( n ) = ∑ d ∣ n g ( d ) ,那么有 𝑔 ( 𝑛 ) = ∑ 𝑑 ∣ 𝑛 𝜇 ( 𝑑 ) 𝑓 ( 𝑛 𝑑 ) g ( n ) = ∑ d ∣ n μ ( d ) f ( n d ) 。
这种形式下,数论函数 𝑓 ( 𝑛 ) f ( n ) 称为数论函数 𝑔 ( 𝑛 ) g ( n ) 的莫比乌斯变换,数论函数 𝑔 ( 𝑛 ) g ( n ) 称为数论函数 𝑓 ( 𝑛 ) f ( n ) 的莫比乌斯逆变换(反演)。
容易看出,数论函数 𝑔 ( 𝑛 ) g ( n ) 的莫比乌斯变换,就是将数论函数 𝑔 ( 𝑛 ) g ( n ) 与常数函数 1 1 进行狄利克雷卷积。
注 根据狄利克雷卷积与狄利克雷生成函数的对应关系,数论函数 𝑔 ( 𝑛 ) g ( n ) 的莫比乌斯变换对应的狄利克雷生成函数,就是数论函数 𝑔 ( 𝑛 ) g ( n ) 的狄利克雷生成函数与黎曼函数 𝜁 ζ 的乘积。
形式二:如果有 𝑓 ( 𝑛 ) = ∑ 𝑛 | 𝑑 𝑔 ( 𝑑 ) f ( n ) = ∑ n | d g ( d ) ,那么有 𝑔 ( 𝑛 ) = ∑ 𝑛 | 𝑑 𝜇 ( 𝑑 𝑛 ) 𝑓 ( 𝑑 ) g ( n ) = ∑ n | d μ ( d n ) f ( d ) 。
证明 方法一:对原式做数论变换。
∑ 𝑑 ∣ 𝑛 𝜇 ( 𝑑 ) 𝑓 ( 𝑛 𝑑 ) = ∑ 𝑑 ∣ 𝑛 𝜇 ( 𝑑 ) ∑ 𝑘 ∣ 𝑛 𝑑 𝑔 ( 𝑘 ) = ∑ 𝑘 ∣ 𝑛 𝑔 ( 𝑘 ) ∑ 𝑑 ∣ 𝑛 𝑘 𝜇 ( 𝑑 ) = 𝑔 ( 𝑛 ) ∑ d ∣ n μ ( d ) f ( n d ) = ∑ d ∣ n μ ( d ) ∑ k ∣ n d g ( k ) = ∑ k ∣ n g ( k ) ∑ d ∣ n k μ ( d ) = g ( n ) 用 ∑ 𝑑 ∣ 𝑛 𝑔 ( 𝑑 ) ∑ d ∣ n g ( d ) 来替换 𝑓 ( 𝑛 𝑑 ) f ( n d ) ,再变换求和顺序。最后一步变换的依据:∑ 𝑑 ∣ 𝑛 𝜇 ( 𝑑 ) = [ 𝑛 = 1 ] ∑ d ∣ n μ ( d ) = [ n = 1 ] ,因此在 𝑛 𝑘 = 1 n k = 1 时第二个和式的值才为 1 1 。此时 𝑛 = 𝑘 n = k ,故原式等价于 ∑ 𝑘 ∣ 𝑛 [ 𝑛 = 𝑘 ] ⋅ 𝑔 ( 𝑘 ) = 𝑔 ( 𝑛 ) ∑ k ∣ n [ n = k ] ⋅ g ( k ) = g ( n )
方法二:运用卷积。
原问题为:已知 𝑓 = 𝑔 ∗ 1 f = g ∗ 1 ,证明 𝑔 = 𝑓 ∗ 𝜇 g = f ∗ μ
易知如下转化:𝑓 ∗ 𝜇 = 𝑔 ∗ 1 ∗ 𝜇 ⟹ 𝑓 ∗ 𝜇 = 𝑔 f ∗ μ = g ∗ 1 ∗ μ ⟹ f ∗ μ = g (其中 1 ∗ 𝜇 = 𝜀 1 ∗ μ = ε )。
对于第二种形式:
类似上面的方法一,我们考虑逆推这个式子。
∑ 𝑛 | 𝑑 𝜇 ( 𝑑 𝑛 ) 𝑓 ( 𝑑 ) = + ∞ ∑ 𝑘 = 1 𝜇 ( 𝑘 ) 𝑓 ( 𝑘 𝑛 ) = + ∞ ∑ 𝑘 = 1 𝜇 ( 𝑘 ) ∑ 𝑘 𝑛 | 𝑑 𝑔 ( 𝑑 ) = ∑ 𝑛 | 𝑑 𝑔 ( 𝑑 ) ∑ 𝑘 | 𝑑 𝑛 𝜇 ( 𝑘 ) = ∑ 𝑛 | 𝑑 𝑔 ( 𝑑 ) 𝜖 ( 𝑑 𝑛 ) = 𝑔 ( 𝑛 ) ∑ n | d μ ( d n ) f ( d ) = ∑ k = 1 + ∞ μ ( k ) f ( k n ) = ∑ k = 1 + ∞ μ ( k ) ∑ k n | d g ( d ) = ∑ n | d g ( d ) ∑ k | d n μ ( k ) = ∑ n | d g ( d ) ϵ ( d n ) = g ( n ) 我们把 𝑑 d 表示为 𝑘 𝑛 k n 的形式,然后把 𝑓 f 的原定义代入式子。
发现枚举 𝑘 k 再枚举 𝑘 𝑛 k n 的倍数可以转换为直接枚举 𝑛 n 的倍数再求出 𝑘 k ,发现后面那一块其实就是 𝜖 ϵ , 整个式子只有在 𝑑 = 𝑛 d = n 的时候才能取到值。
问题形式 求值(多组数据)
𝑛 ∑ 𝑖 = 𝑥 𝑚 ∑ 𝑗 = 𝑦 [ g c d ( 𝑖 , 𝑗 ) = 𝑘 ] ( 1 ⩽ 𝑇 , 𝑥 , 𝑦 , 𝑛 , 𝑚 , 𝑘 ⩽ 5 × 1 0 4 ) ∑ i = x n ∑ j = y m [ gcd ( i , j ) = k ] ( 1 ⩽ T , x , y , n , m , k ⩽ 5 × 10 4 ) 根据容斥原理,原式可以分成 4 4 块来处理,每一块的式子都为
𝑛 ∑ 𝑖 = 1 𝑚 ∑ 𝑗 = 1 [ g c d ( 𝑖 , 𝑗 ) = 𝑘 ] ∑ i = 1 n ∑ j = 1 m [ gcd ( i , j ) = k ] 考虑化简该式子
⌊ 𝑛 𝑘 ⌋ ∑ 𝑖 = 1 ⌊ 𝑚 𝑘 ⌋ ∑ 𝑗 = 1 [ g c d ( 𝑖 , 𝑗 ) = 1 ] ∑ i = 1 ⌊ n k ⌋ ∑ j = 1 ⌊ m k ⌋ [ gcd ( i , j ) = 1 ] 因为 g c d ( 𝑖 , 𝑗 ) = 1 gcd ( i , j ) = 1 时对答案才用贡献,于是我们可以将其替换为 𝜀 ( g c d ( 𝑖 , 𝑗 ) ) ε ( gcd ( i , j ) ) (𝜀 ( 𝑛 ) ε ( n ) 当且仅当 𝑛 = 1 n = 1 时值为 1 1 否则为 0 0 ),故原式化为
⌊ 𝑛 𝑘 ⌋ ∑ 𝑖 = 1 ⌊ 𝑚 𝑘 ⌋ ∑ 𝑗 = 1 𝜀 ( g c d ( 𝑖 , 𝑗 ) ) ∑ i = 1 ⌊ n k ⌋ ∑ j = 1 ⌊ m k ⌋ ε ( gcd ( i , j ) ) 将 𝜀 ε 函数展开得到
⌊ 𝑛 𝑘 ⌋ ∑ 𝑖 = 1 ⌊ 𝑚 𝑘 ⌋ ∑ 𝑗 = 1 ∑ 𝑑 ∣ g c d ( 𝑖 , 𝑗 ) 𝜇 ( 𝑑 ) ∑ i = 1 ⌊ n k ⌋ ∑ j = 1 ⌊ m k ⌋ ∑ d ∣ gcd ( i , j ) μ ( d ) 变换求和顺序,先枚举 𝑑 ∣ g c d ( 𝑖 , 𝑗 ) d ∣ gcd ( i , j ) 可得
∑ 𝑑 = 1 𝜇 ( 𝑑 ) ⌊ 𝑛 𝑘 ⌋ ∑ 𝑖 = 1 [ 𝑑 ∣ 𝑖 ] ⌊ 𝑚 𝑘 ⌋ ∑ 𝑗 = 1 [ 𝑑 ∣ 𝑗 ] ∑ d = 1 μ ( d ) ∑ i = 1 ⌊ n k ⌋ [ d ∣ i ] ∑ j = 1 ⌊ m k ⌋ [ d ∣ j ] 易知 1 ∼ ⌊ 𝑛 𝑘 ⌋ 1 ∼ ⌊ n k ⌋ 中 𝑑 d 的倍数有 ⌊ 𝑛 𝑘 𝑑 ⌋ ⌊ n k d ⌋ 个,故原式化为
m i n ( ⌊ 𝑛 𝑘 ⌋ , ⌊ 𝑚 𝑘 ⌋ ) ∑ 𝑑 = 1 𝜇 ( 𝑑 ) ⌊ 𝑛 𝑘 𝑑 ⌋ ⌊ 𝑚 𝑘 𝑑 ⌋ ∑ d = 1 min ( ⌊ n k ⌋ , ⌊ m k ⌋ ) μ ( d ) ⌊ n k d ⌋ ⌊ m k d ⌋ 很显然,式子可以数论分块求解。
时间复杂度 Θ ( 𝑁 + 𝑇 √ 𝑛 ) Θ ( N + T n )
代码实现 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53 #include <algorithm>
#include <iostream>
using namespace std ;
constexpr int N = 50000 ;
int mu [ N + 5 ], p [ N + 5 ];
bool flg [ N + 5 ];
void init () {
int tot = 0 ;
mu [ 1 ] = 1 ;
for ( int i = 2 ; i <= N ; ++ i ) {
if ( ! flg [ i ]) {
p [ ++ tot ] = i ;
mu [ i ] = -1 ;
}
for ( int j = 1 ; j <= tot && i * p [ j ] <= N ; ++ j ) {
flg [ i * p [ j ]] = true ;
if ( i % p [ j ] == 0 ) {
mu [ i * p [ j ]] = 0 ;
break ;
}
mu [ i * p [ j ]] = - mu [ i ];
}
}
for ( int i = 1 ; i <= N ; ++ i ) mu [ i ] += mu [ i - 1 ];
}
int solve ( int n , int m ) {
int res = 0 ;
for ( int i = 1 , j ; i <= min ( n , m ); i = j + 1 ) {
j = min ( n / ( n / i ), m / ( m / i ));
res += ( mu [ j ] - mu [ i - 1 ]) * ( n / i ) * ( m / i ); // 代推出来的式子
}
return res ;
}
int main () {
cin . tie ( nullptr ) -> sync_with_stdio ( false );
int T , a , b , c , d , k ;
init (); // 预处理mu数组
cin >> T ;
for ( int i = 1 ; i <= T ; i ++ ) {
cin >> a >> b >> c >> d >> k ;
// 根据容斥原理,1<=x<=b&&1<=y<=d范围中的答案数减去1<=x<=b&&1<=y<=c-1范围中的答案数和
// 1<=x<=a-1&&1<=y<=d范围中的答案数再加上1<=x<=a-1&&1<=y<=c-1范围中的答案数
// 即可得到a<=x<=b&&c<=y<=d范围中的答案数
// 这一步如果不懂可以画坐标图进行理解
cout << solve ( b / k , d / k ) - solve ( b / k , ( c - 1 ) / k ) -
solve (( a - 1 ) / k , d / k ) + solve (( a - 1 ) / k , ( c - 1 ) / k )
<< '\n' ;
}
return 0 ;
}
求值(多组数据)
𝑛 ∑ 𝑖 = 1 l c m ( 𝑖 , 𝑛 ) s . t . 1 ⩽ 𝑇 ⩽ 3 × 1 0 5 , 1 ⩽ 𝑛 ⩽ 1 0 6 ∑ i = 1 n lcm ( i , n ) s.t. 1 ⩽ T ⩽ 3 × 10 5 , 1 ⩽ n ⩽ 10 6 易得原式即
𝑛 ∑ 𝑖 = 1 𝑖 ⋅ 𝑛 g c d ( 𝑖 , 𝑛 ) ∑ i = 1 n i ⋅ n gcd ( i , n ) 将原式复制一份并且颠倒顺序,然后将 n 一项单独提出,可得
1 2 ⋅ ( 𝑛 − 1 ∑ 𝑖 = 1 𝑖 ⋅ 𝑛 g c d ( 𝑖 , 𝑛 ) + 1 ∑ 𝑖 = 𝑛 − 1 𝑖 ⋅ 𝑛 g c d ( 𝑖 , 𝑛 ) ) + 𝑛 1 2 ⋅ ( ∑ i = 1 n − 1 i ⋅ n gcd ( i , n ) + ∑ i = n − 1 1 i ⋅ n gcd ( i , n ) ) + n 根据 g c d ( 𝑖 , 𝑛 ) = g c d ( 𝑛 − 𝑖 , 𝑛 ) gcd ( i , n ) = gcd ( n − i , n ) ,可将原式化为
1 2 ⋅ ( 𝑛 − 1 ∑ 𝑖 = 1 𝑖 ⋅ 𝑛 g c d ( 𝑖 , 𝑛 ) + 1 ∑ 𝑖 = 𝑛 − 1 𝑖 ⋅ 𝑛 g c d ( 𝑛 − 𝑖 , 𝑛 ) ) + 𝑛 1 2 ⋅ ( ∑ i = 1 n − 1 i ⋅ n gcd ( i , n ) + ∑ i = n − 1 1 i ⋅ n gcd ( n − i , n ) ) + n 两个求和式中分母相同的项可以合并。
1 2 ⋅ 𝑛 − 1 ∑ 𝑖 = 1 𝑛 2 g c d ( 𝑖 , 𝑛 ) + 𝑛 1 2 ⋅ ∑ i = 1 n − 1 n 2 gcd ( i , n ) + n 即
1 2 ⋅ 𝑛 ∑ 𝑖 = 1 𝑛 2 g c d ( 𝑖 , 𝑛 ) + 𝑛 2 1 2 ⋅ ∑ i = 1 n n 2 gcd ( i , n ) + n 2 可以将相同的 g c d ( 𝑖 , 𝑛 ) gcd ( i , n ) 合并在一起计算,故只需要统计 g c d ( 𝑖 , 𝑛 ) = 𝑑 gcd ( i , n ) = d 的个数。当 g c d ( 𝑖 , 𝑛 ) = 𝑑 gcd ( i , n ) = d 时,g c d ( 𝑖 𝑑 , 𝑛 𝑑 ) = 1 gcd ( i d , n d ) = 1 ,所以 g c d ( 𝑖 , 𝑛 ) = 𝑑 gcd ( i , n ) = d 的个数有 𝜑 ( 𝑛 𝑑 ) φ ( n d ) 个。
故答案为
1 2 ⋅ ∑ 𝑑 ∣ 𝑛 𝑛 2 ⋅ 𝜑 ( 𝑛 𝑑 ) 𝑑 + 𝑛 2 1 2 ⋅ ∑ d ∣ n n 2 ⋅ φ ( n d ) d + n 2 变换求和顺序,设 𝑑 ′ = 𝑛 𝑑 d ′ = n d ,合并公因式,式子化为
1 2 𝑛 ⋅ ⎛ ⎜ ⎜ ⎝ ∑ 𝑑 ′ ∣ 𝑛 𝑑 ′ ⋅ 𝜑 ( 𝑑 ′ ) + 1 ⎞ ⎟ ⎟ ⎠ 1 2 n ⋅ ( ∑ d ′ ∣ n d ′ ⋅ φ ( d ′ ) + 1 ) 设 g ( 𝑛 ) = ∑ 𝑑 ∣ 𝑛 𝑑 ⋅ 𝜑 ( 𝑑 ) g ( n ) = ∑ d ∣ n d ⋅ φ ( d ) ,已知 g g 为积性函数,于是可以 Θ ( 𝑛 ) Θ ( n ) 筛出。每次询问 Θ ( 1 ) Θ ( 1 ) 计算即可。
下面给出这个函数筛法的推导过程:
首先考虑 g ( 𝑝 𝑘 𝑗 ) g ( p j k ) 的值,显然它的约数只有 𝑝 0 𝑗 , 𝑝 1 𝑗 , ⋯ , 𝑝 𝑘 𝑗 p j 0 , p j 1 , ⋯ , p j k ,因此
g ( 𝑝 𝑘 𝑗 ) = 𝑘 ∑ 𝑤 = 0 𝑝 𝑤 𝑗 ⋅ 𝜑 ( 𝑝 𝑤 𝑗 ) g ( p j k ) = ∑ w = 0 k p j w ⋅ φ ( p j w ) 又有 𝜑 ( 𝑝 𝑤 𝑗 ) = 𝑝 𝑤 − 1 𝑗 ⋅ ( 𝑝 𝑗 − 1 ) φ ( p j w ) = p j w − 1 ⋅ ( p j − 1 ) ,则原式可化为
𝑘 ∑ 𝑤 = 0 𝑝 2 𝑤 − 1 𝑗 ⋅ ( 𝑝 𝑗 − 1 ) ∑ w = 0 k p j 2 w − 1 ⋅ ( p j − 1 ) 于是有
g ( 𝑝 𝑘 + 1 𝑗 ) = g ( 𝑝 𝑘 𝑗 ) + 𝑝 2 𝑘 + 1 𝑗 ⋅ ( 𝑝 𝑗 − 1 ) g ( p j k + 1 ) = g ( p j k ) + p j 2 k + 1 ⋅ ( p j − 1 ) 那么,对于线性筛中的 g ( 𝑖 ⋅ 𝑝 𝑗 ) ( 𝑝 𝑗 | 𝑖 ) g ( i ⋅ p j ) ( p j | i ) ,令 𝑖 = 𝑎 ⋅ 𝑝 𝑤 𝑗 ( g c d ( 𝑎 , 𝑝 𝑗 ) = 1 ) i = a ⋅ p j w ( gcd ( a , p j ) = 1 ) ,可得
g ( 𝑖 ⋅ 𝑝 𝑗 ) = g ( 𝑎 ) ⋅ g ( 𝑝 𝑤 + 1 𝑗 ) g ( i ⋅ p j ) = g ( a ) ⋅ g ( p j w + 1 ) g ( 𝑖 ) = g ( 𝑎 ) ⋅ g ( 𝑝 𝑤 𝑗 ) g ( i ) = g ( a ) ⋅ g ( p j w ) 即
g ( 𝑖 ⋅ 𝑝 𝑗 ) − g ( 𝑖 ) = g ( 𝑎 ) ⋅ 𝑝 2 𝑤 + 1 𝑗 ⋅ ( 𝑝 𝑗 − 1 ) g ( i ⋅ p j ) − g ( i ) = g ( a ) ⋅ p j 2 w + 1 ⋅ ( p j − 1 ) 同理有
g ( 𝑖 ) − g ( 𝑖 𝑝 𝑗 ) = g ( 𝑎 ) ⋅ 𝑝 2 𝑤 − 1 𝑗 ⋅ ( 𝑝 𝑗 − 1 ) g ( i ) − g ( i p j ) = g ( a ) ⋅ p j 2 w − 1 ⋅ ( p j − 1 ) 因此
g ( 𝑖 ⋅ 𝑝 𝑗 ) = g ( 𝑖 ) + ( g ( 𝑖 ) − g ( 𝑖 𝑝 𝑗 ) ) ⋅ 𝑝 2 𝑗 g ( i ⋅ p j ) = g ( i ) + ( g ( i ) − g ( i p j ) ) ⋅ p j 2 时间复杂度 :Θ ( 𝑛 + 𝑇 ) Θ ( n + T )
代码实现 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39 #include <iostream>
constexpr int N = 1000000 ;
int tot , p [ N + 5 ];
long long g [ N + 5 ];
bool flg [ N + 5 ]; // 标记数组
void solve () {
g [ 1 ] = 1 ;
for ( int i = 2 ; i <= N ; ++ i ) {
if ( ! flg [ i ]) {
p [ ++ tot ] = i ;
g [ i ] = ( long long ) 1 * i * ( i - 1 ) + 1 ;
}
for ( int j = 1 ; j <= tot && i * p [ j ] <= N ; ++ j ) {
flg [ i * p [ j ]] = true ;
if ( i % p [ j ] == 0 ) {
g [ i * p [ j ]] =
g [ i ] + ( g [ i ] - g [ i / p [ j ]]) * p [ j ] * p [ j ]; // 代入推出来的式子
break ;
}
g [ i * p [ j ]] = g [ i ] * g [ p [ j ]];
}
}
}
using std :: cin ;
using std :: cout ;
int main () {
cin . tie ( nullptr ) -> sync_with_stdio ( false );
int T , n ;
solve (); // 预处理g数组
cin >> T ;
for ( int i = 1 ; i <= T ; ++ i ) {
cin >> n ;
cout << ( g [ n ] + 1 ) * n / 2 << '\n' ;
}
return 0 ;
}
求值(对 2 0 1 0 1 0 0 9 20101009 取模)
𝑛 ∑ 𝑖 = 1 𝑚 ∑ 𝑗 = 1 l c m ( 𝑖 , 𝑗 ) ( 𝑛 , 𝑚 ⩽ 1 0 7 ) ∑ i = 1 n ∑ j = 1 m lcm ( i , j ) ( n , m ⩽ 10 7 ) 易知原式等价于
𝑛 ∑ 𝑖 = 1 𝑚 ∑ 𝑗 = 1 𝑖 ⋅ 𝑗 g c d ( 𝑖 , 𝑗 ) ∑ i = 1 n ∑ j = 1 m i ⋅ j gcd ( i , j ) 枚举最大公因数 𝑑 d ,显然两个数除以 𝑑 d 得到的数互质
𝑛 ∑ 𝑖 = 1 𝑚 ∑ 𝑗 = 1 ∑ 𝑑 ∣ 𝑖 , 𝑑 ∣ 𝑗 , g c d ( 𝑖 𝑑 , 𝑗 𝑑 ) = 1 𝑖 ⋅ 𝑗 𝑑 ∑ i = 1 n ∑ j = 1 m ∑ d ∣ i , d ∣ j , gcd ( i d , j d ) = 1 i ⋅ j d 非常经典的 g c d gcd 式子的化法
𝑛 ∑ 𝑑 = 1 𝑑 ⋅ ⌊ 𝑛 𝑑 ⌋ ∑ 𝑖 = 1 ⌊ 𝑚 𝑑 ⌋ ∑ 𝑗 = 1 [ g c d ( 𝑖 , 𝑗 ) = 1 ] 𝑖 ⋅ 𝑗 ∑ d = 1 n d ⋅ ∑ i = 1 ⌊ n d ⌋ ∑ j = 1 ⌊ m d ⌋ [ gcd ( i , j ) = 1 ] i ⋅ j 后半段式子中,出现了互质数对之积的和,为了让式子更简洁就把它拿出来单独计算。于是我们记
s u m ( 𝑛 , 𝑚 ) = 𝑛 ∑ 𝑖 = 1 𝑚 ∑ 𝑗 = 1 [ g c d ( 𝑖 , 𝑗 ) = 1 ] 𝑖 ⋅ 𝑗 sum ( n , m ) = ∑ i = 1 n ∑ j = 1 m [ gcd ( i , j ) = 1 ] i ⋅ j 接下来对 s u m ( 𝑛 , 𝑚 ) sum ( n , m ) 进行化简。首先枚举约数,并将 [ g c d ( 𝑖 , 𝑗 ) = 1 ] [ gcd ( i , j ) = 1 ] 表示为 𝜀 ( g c d ( 𝑖 , 𝑗 ) ) ε ( gcd ( i , j ) )
𝑛 ∑ 𝑑 = 1 𝑛 ∑ 𝑑 ∣ 𝑖 𝑚 ∑ 𝑑 ∣ 𝑗 𝜇 ( 𝑑 ) ⋅ 𝑖 ⋅ 𝑗 ∑ d = 1 n ∑ d ∣ i n ∑ d ∣ j m μ ( d ) ⋅ i ⋅ j 设 𝑖 = 𝑖 ′ ⋅ 𝑑 i = i ′ ⋅ d ,𝑗 = 𝑗 ′ ⋅ 𝑑 j = j ′ ⋅ d ,显然式子可以变为
𝑛 ∑ 𝑑 = 1 𝜇 ( 𝑑 ) ⋅ 𝑑 2 ⋅ ⌊ 𝑛 𝑑 ⌋ ∑ 𝑖 = 1 ⌊ 𝑚 𝑑 ⌋ ∑ 𝑗 = 1 𝑖 ⋅ 𝑗 ∑ d = 1 n μ ( d ) ⋅ d 2 ⋅ ∑ i = 1 ⌊ n d ⌋ ∑ j = 1 ⌊ m d ⌋ i ⋅ j 观察上式,前半段可以预处理前缀和;后半段又是一个范围内数对之和,记
𝑔 ( 𝑛 , 𝑚 ) = 𝑛 ∑ 𝑖 = 1 𝑚 ∑ 𝑗 = 1 𝑖 ⋅ 𝑗 = 𝑛 ⋅ ( 𝑛 + 1 ) 2 × 𝑚 ⋅ ( 𝑚 + 1 ) 2 g ( n , m ) = ∑ i = 1 n ∑ j = 1 m i ⋅ j = n ⋅ ( n + 1 ) 2 × m ⋅ ( m + 1 ) 2 可以 Θ ( 1 ) Θ ( 1 ) 求解
至此
s u m ( 𝑛 , 𝑚 ) = 𝑛 ∑ 𝑑 = 1 𝜇 ( 𝑑 ) ⋅ 𝑑 2 ⋅ 𝑔 ( ⌊ 𝑛 𝑑 ⌋ , ⌊ 𝑚 𝑑 ⌋ ) sum ( n , m ) = ∑ d = 1 n μ ( d ) ⋅ d 2 ⋅ g ( ⌊ n d ⌋ , ⌊ m d ⌋ ) 我们可以 ⌊ 𝑛 ⌊ 𝑛 𝑑 ⌋ ⌋ ⌊ n ⌊ n d ⌋ ⌋ 数论分块求解 s u m ( 𝑛 , 𝑚 ) sum ( n , m ) 函数。
在求出 s u m ( 𝑛 , 𝑚 ) sum ( n , m ) 后,回到定义 s u m sum 的地方,可得原式为
𝑛 ∑ 𝑑 = 1 𝑑 ⋅ s u m ( ⌊ 𝑛 𝑑 ⌋ , ⌊ 𝑚 𝑑 ⌋ ) ∑ d = 1 n d ⋅ sum ( ⌊ n d ⌋ , ⌊ m d ⌋ ) 可见这又是一个可以数论分块求解的式子!
本题除了推式子比较复杂、代码细节较多之外,是一道很好的莫比乌斯反演练习题!(上述过程中,默认 𝑛 ⩽ 𝑚 n ⩽ m )
时间复杂度:Θ ( 𝑛 + 𝑚 ) Θ ( n + m ) (瓶颈为线性筛)
代码实现 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64 #include <algorithm>
#include <iostream>
using namespace std ;
constexpr int N = 1e7 ;
constexpr int mod = 20101009 ;
int n , m , mu [ N + 5 ], p [ N / 10 + 5 ], sum [ N + 5 ];
bool flg [ N + 5 ];
int Sum ( int x , int y ) {
return (( long long ) 1 * x * ( x + 1 ) / 2 % mod ) *
(( long long ) 1 * y * ( y + 1 ) / 2 % mod ) % mod ;
}
int func ( int x , int y ) {
int res = 0 ;
int j ;
for ( int i = 1 ; i <= min ( x , y ); i = j + 1 ) {
j = min ( x / ( x / i ), y / ( y / i ));
res = ( res + ( long long ) 1 * ( sum [ j ] - sum [ i - 1 ] + mod ) *
Sum ( x / i , y / i ) % mod ) %
mod ; //+mod防负数
}
return res ;
}
int solve ( int x , int y ) {
int res = 0 ;
int j ;
for ( int i = 1 ; i <= min ( x , y ); i = j + 1 ) { // 整除分块处理
j = min ( x / ( x / i ), y / ( y / i ));
res = ( res + ( long long ) 1 * ( j - i + 1 ) * ( i + j ) / 2 % mod *
func ( x / i , y / i ) % mod ) %
mod ; // !每步取模防爆
}
return res ;
}
void init () { // 线性筛
mu [ 1 ] = 1 ;
int tot = 0 , k = min ( n , m );
for ( int i = 2 ; i <= k ; ++ i ) {
if ( ! flg [ i ]) {
p [ ++ tot ] = i ;
mu [ i ] = -1 ;
}
for ( int j = 1 ; j <= tot && i * p [ j ] <= k ; ++ j ) {
flg [ i * p [ j ]] = true ;
if ( i % p [ j ] == 0 ) {
mu [ i * p [ j ]] = 0 ;
break ;
}
mu [ i * p [ j ]] = - mu [ i ];
}
}
for ( int i = 1 ; i <= k ; ++ i )
sum [ i ] = ( sum [ i - 1 ] + ( long long ) 1 * i * i % mod * ( mu [ i ] + mod )) % mod ;
}
int main () {
cin >> n >> m ;
init ();
cout << solve ( n , m ) << '\n' ;
}
多组数据,求
𝑛 ∑ 𝑖 = 1 𝑚 ∑ 𝑗 = 1 𝑑 ( 𝑖 ⋅ 𝑗 ) ( 𝑛 , 𝑚 , 𝑇 ≤ 5 × 1 0 4 ) ∑ i = 1 n ∑ j = 1 m d ( i ⋅ j ) ( n , m , T ≤ 5 × 10 4 ) 其中 𝑑 ( 𝑛 ) = ∑ 𝑖 ∣ 𝑛 1 d ( n ) = ∑ i ∣ n 1 ,𝑑 ( 𝑛 ) d ( n ) 表示 𝑛 n 的约数个数
要推这道题首先要了解 𝑑 d 函数的一个特殊性质
𝑑 ( 𝑖 ⋅ 𝑗 ) = ∑ 𝑥 ∣ 𝑖 ∑ 𝑦 ∣ 𝑗 [ g c d ( 𝑥 , 𝑦 ) = 1 ] d ( i ⋅ j ) = ∑ x ∣ i ∑ y ∣ j [ gcd ( x , y ) = 1 ] 再化一下这个式子
𝑑 ( 𝑖 ⋅ 𝑗 ) = ∑ 𝑥 ∣ 𝑖 ∑ 𝑦 ∣ 𝑗 [ g c d ( 𝑥 , 𝑦 ) = 1 ] = ∑ 𝑥 ∣ 𝑖 ∑ 𝑦 ∣ 𝑗 ∑ 𝑝 ∣ g c d ( 𝑥 , 𝑦 ) 𝜇 ( 𝑝 ) = 𝑚 𝑖 𝑛 ( 𝑖 , 𝑗 ) ∑ 𝑝 = 1 ∑ 𝑥 ∣ 𝑖 ∑ 𝑦 ∣ 𝑗 [ 𝑝 ∣ g c d ( 𝑥 , 𝑦 ) ] ⋅ 𝜇 ( 𝑝 ) = ∑ 𝑝 ∣ 𝑖 , 𝑝 ∣ 𝑗 𝜇 ( 𝑝 ) ∑ 𝑥 ∣ 𝑖 ∑ 𝑦 ∣ 𝑗 [ 𝑝 ∣ g c d ( 𝑥 , 𝑦 ) ] = ∑ 𝑝 ∣ 𝑖 , 𝑝 ∣ 𝑗 𝜇 ( 𝑝 ) ∑ 𝑥 ∣ 𝑖 𝑝 ∑ 𝑦 ∣ 𝑗 𝑝 1 = ∑ 𝑝 ∣ 𝑖 , 𝑝 ∣ 𝑗 𝜇 ( 𝑝 ) 𝑑 ( 𝑖 𝑝 ) 𝑑 ( 𝑗 𝑝 ) d ( i ⋅ j ) = ∑ x ∣ i ∑ y ∣ j [ gcd ( x , y ) = 1 ] = ∑ x ∣ i ∑ y ∣ j ∑ p ∣ gcd ( x , y ) μ ( p ) = ∑ p = 1 m i n ( i , j ) ∑ x ∣ i ∑ y ∣ j [ p ∣ gcd ( x , y ) ] ⋅ μ ( p ) = ∑ p ∣ i , p ∣ j μ ( p ) ∑ x ∣ i ∑ y ∣ j [ p ∣ gcd ( x , y ) ] = ∑ p ∣ i , p ∣ j μ ( p ) ∑ x ∣ i p ∑ y ∣ j p 1 = ∑ p ∣ i , p ∣ j μ ( p ) d ( i p ) d ( j p ) 将上述式子代回原式
𝑛 ∑ 𝑖 = 1 𝑚 ∑ 𝑗 = 1 𝑑 ( 𝑖 ⋅ 𝑗 ) = 𝑛 ∑ 𝑖 = 1 𝑚 ∑ 𝑗 = 1 ∑ 𝑝 ∣ 𝑖 , 𝑝 ∣ 𝑗 𝜇 ( 𝑝 ) 𝑑 ( 𝑖 𝑝 ) 𝑑 ( 𝑗 𝑝 ) = 𝑚 𝑖 𝑛 ( 𝑛 , 𝑚 ) ∑ 𝑝 = 1 𝑛 ∑ 𝑖 = 1 𝑚 ∑ 𝑗 = 1 [ 𝑝 ∣ 𝑖 , 𝑝 ∣ 𝑗 ] ⋅ 𝜇 ( 𝑝 ) 𝑑 ( 𝑖 𝑝 ) 𝑑 ( 𝑗 𝑝 ) = 𝑚 𝑖 𝑛 ( 𝑛 , 𝑚 ) ∑ 𝑝 = 1 ⌊ 𝑛 𝑝 ⌋ ∑ 𝑖 = 1 ⌊ 𝑚 𝑝 ⌋ ∑ 𝑗 = 1 𝜇 ( 𝑝 ) 𝑑 ( 𝑖 ) 𝑑 ( 𝑗 ) = 𝑚 𝑖 𝑛 ( 𝑛 , 𝑚 ) ∑ 𝑝 = 1 𝜇 ( 𝑝 ) ⌊ 𝑛 𝑝 ⌋ ∑ 𝑖 = 1 𝑑 ( 𝑖 ) ⌊ 𝑚 𝑝 ⌋ ∑ 𝑗 = 1 𝑑 ( 𝑗 ) = 𝑚 𝑖 𝑛 ( 𝑛 , 𝑚 ) ∑ 𝑝 = 1 𝜇 ( 𝑝 ) 𝑆 ( ⌊ 𝑛 𝑝 ⌋ ) 𝑆 ( ⌊ 𝑚 𝑝 ⌋ ) ( 𝑆 ( 𝑛 ) = 𝑛 ∑ 𝑖 = 1 𝑑 ( 𝑖 ) ) ∑ i = 1 n ∑ j = 1 m d ( i ⋅ j ) = ∑ i = 1 n ∑ j = 1 m ∑ p ∣ i , p ∣ j μ ( p ) d ( i p ) d ( j p ) = ∑ p = 1 m i n ( n , m ) ∑ i = 1 n ∑ j = 1 m [ p ∣ i , p ∣ j ] ⋅ μ ( p ) d ( i p ) d ( j p ) = ∑ p = 1 m i n ( n , m ) ∑ i = 1 ⌊ n p ⌋ ∑ j = 1 ⌊ m p ⌋ μ ( p ) d ( i ) d ( j ) = ∑ p = 1 m i n ( n , m ) μ ( p ) ∑ i = 1 ⌊ n p ⌋ d ( i ) ∑ j = 1 ⌊ m p ⌋ d ( j ) = ∑ p = 1 m i n ( n , m ) μ ( p ) S ( ⌊ n p ⌋ ) S ( ⌊ m p ⌋ ) ( S ( n ) = ∑ i = 1 n d ( i ) ) 那么 𝑂 ( 𝑛 ) O ( n ) 预处理 𝜇 , 𝑑 μ , d 的前缀和,𝑂 ( √ 𝑛 ) O ( n ) 分块处理询问,总复杂度 𝑂 ( 𝑛 + 𝑇 √ 𝑛 ) O ( n + T n ) .
代码实现 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49 #include <algorithm>
#include <iostream>
using namespace std ;
constexpr long long N = 5e4 + 5 ;
long long n , m , T , pr [ N ], mu [ N ], d [ N ], t [ N ],
cnt ; // t 表示 i 的最小质因子出现的次数
bool bp [ N ];
void prime_work ( long long k ) {
bp [ 0 ] = bp [ 1 ] = true , mu [ 1 ] = 1 , d [ 1 ] = 1 ;
for ( long long i = 2 ; i <= k ; i ++ ) { // 线性筛
if ( ! bp [ i ]) pr [ ++ cnt ] = i , mu [ i ] = -1 , d [ i ] = 2 , t [ i ] = 1 ;
for ( long long j = 1 ; j <= cnt && i * pr [ j ] <= k ; j ++ ) {
bp [ i * pr [ j ]] = true ;
if ( i % pr [ j ] == 0 ) {
mu [ i * pr [ j ]] = 0 ;
d [ i * pr [ j ]] = d [ i ] / ( t [ i ] + 1 ) * ( t [ i ] + 2 );
t [ i * pr [ j ]] = t [ i ] + 1 ;
break ;
} else {
mu [ i * pr [ j ]] = - mu [ i ];
d [ i * pr [ j ]] = d [ i ] << 1 ;
t [ i * pr [ j ]] = 1 ;
}
}
}
for ( long long i = 2 ; i <= k ; i ++ )
mu [ i ] += mu [ i - 1 ], d [ i ] += d [ i - 1 ]; // 求前缀和
}
long long solve () {
long long res = 0 , mxi = min ( n , m );
for ( long long i = 1 , j ; i <= mxi ; i = j + 1 ) { // 整除分块
j = min ( n / ( n / i ), m / ( m / i ));
res += d [ n / i ] * d [ m / i ] * ( mu [ j ] - mu [ i - 1 ]);
}
return res ;
}
int main () {
cin . tie ( nullptr ) -> sync_with_stdio ( false );
cin >> T ;
prime_work ( 50000 ); // 预处理
while ( T -- ) {
cin >> n >> m ;
cout << solve () << '\n' ;
}
return 0 ;
}
莫比乌斯反演扩展 结尾补充一个莫比乌斯反演的非卷积形式。
对于数论函数 𝑓 , 𝑔 f , g 和完全积性函数 𝑡 t 且 𝑡 ( 1 ) = 1 t ( 1 ) = 1 :
𝑓 ( 𝑛 ) = 𝑛 ∑ 𝑖 = 1 𝑡 ( 𝑖 ) 𝑔 ( ⌊ 𝑛 𝑖 ⌋ ) ⟺ 𝑔 ( 𝑛 ) = 𝑛 ∑ 𝑖 = 1 𝜇 ( 𝑖 ) 𝑡 ( 𝑖 ) 𝑓 ( ⌊ 𝑛 𝑖 ⌋ ) f ( n ) = ∑ i = 1 n t ( i ) g ( ⌊ n i ⌋ ) ⟺ g ( n ) = ∑ i = 1 n μ ( i ) t ( i ) f ( ⌊ n i ⌋ ) 我们证明一下
𝑔 ( 𝑛 ) = 𝑛 ∑ 𝑖 = 1 𝜇 ( 𝑖 ) 𝑡 ( 𝑖 ) 𝑓 ( ⌊ 𝑛 𝑖 ⌋ ) = 𝑛 ∑ 𝑖 = 1 𝜇 ( 𝑖 ) 𝑡 ( 𝑖 ) ⌊ 𝑛 𝑖 ⌋ ∑ 𝑗 = 1 𝑡 ( 𝑗 ) 𝑔 ( ⌊ ⌊ 𝑛 𝑖 ⌋ 𝑗 ⌋ ) = 𝑛 ∑ 𝑖 = 1 𝜇 ( 𝑖 ) 𝑡 ( 𝑖 ) ⌊ 𝑛 𝑖 ⌋ ∑ 𝑗 = 1 𝑡 ( 𝑗 ) 𝑔 ( ⌊ 𝑛 𝑖 𝑗 ⌋ ) = 𝑛 ∑ 𝑇 = 1 𝑛 ∑ 𝑖 = 1 𝜇 ( 𝑖 ) 𝑡 ( 𝑖 ) ⌊ 𝑛 𝑖 ⌋ ∑ 𝑗 = 1 [ 𝑖 𝑗 = 𝑇 ] 𝑡 ( 𝑗 ) 𝑔 ( ⌊ 𝑛 𝑇 ⌋ ) 【先枚举 i j 乘积】 = 𝑛 ∑ 𝑇 = 1 ∑ 𝑖 ∣ 𝑇 𝜇 ( 𝑖 ) 𝑡 ( 𝑖 ) 𝑡 ( 𝑇 𝑖 ) 𝑔 ( ⌊ 𝑛 𝑇 ⌋ ) 【 ⌊ 𝑛 𝑖 ⌋ ∑ 𝑗 = 1 [ 𝑖 𝑗 = 𝑇 ] 对答案的贡献为 1 ,于是省略】 = 𝑛 ∑ 𝑇 = 1 𝑔 ( ⌊ 𝑛 𝑇 ⌋ ) ∑ 𝑖 ∣ 𝑇 𝜇 ( 𝑖 ) 𝑡 ( 𝑖 ) 𝑡 ( 𝑇 𝑖 ) = 𝑛 ∑ 𝑇 = 1 𝑔 ( ⌊ 𝑛 𝑇 ⌋ ) ∑ 𝑖 ∣ 𝑇 𝜇 ( 𝑖 ) 𝑡 ( 𝑇 ) 【 t 是完全积性函数】 = 𝑛 ∑ 𝑇 = 1 𝑔 ( ⌊ 𝑛 𝑇 ⌋ ) 𝑡 ( 𝑇 ) ∑ 𝑖 ∣ 𝑇 𝜇 ( 𝑖 ) = 𝑛 ∑ 𝑇 = 1 𝑔 ( ⌊ 𝑛 𝑇 ⌋ ) 𝑡 ( 𝑇 ) 𝜀 ( 𝑇 ) 【 𝜇 ∗ 1 = 𝜀 】 = 𝑔 ( 𝑛 ) 𝑡 ( 1 ) 【当且仅当 T = 1 , 𝜀 ( 𝑇 ) = 1 时】 = 𝑔 ( 𝑛 ) ◻ g ( n ) = ∑ i = 1 n μ ( i ) t ( i ) f ( ⌊ n i ⌋ ) = ∑ i = 1 n μ ( i ) t ( i ) ∑ j = 1 ⌊ n i ⌋ t ( j ) g ( ⌊ ⌊ n i ⌋ j ⌋ ) = ∑ i = 1 n μ ( i ) t ( i ) ∑ j = 1 ⌊ n i ⌋ t ( j ) g ( ⌊ n i j ⌋ ) = ∑ T = 1 n ∑ i = 1 n μ ( i ) t ( i ) ∑ j = 1 ⌊ n i ⌋ [ i j = T ] t ( j ) g ( ⌊ n T ⌋ ) 【先枚举 ij 乘积】 = ∑ T = 1 n ∑ i ∣ T μ ( i ) t ( i ) t ( T i ) g ( ⌊ n T ⌋ ) 【 ∑ j = 1 ⌊ n i ⌋ [ i j = T ] 对答案的贡献为 1,于是省略】 = ∑ T = 1 n g ( ⌊ n T ⌋ ) ∑ i ∣ T μ ( i ) t ( i ) t ( T i ) = ∑ T = 1 n g ( ⌊ n T ⌋ ) ∑ i ∣ T μ ( i ) t ( T ) 【t 是完全积性函数】 = ∑ T = 1 n g ( ⌊ n T ⌋ ) t ( T ) ∑ i ∣ T μ ( i ) = ∑ T = 1 n g ( ⌊ n T ⌋ ) t ( T ) ε ( T ) 【 μ ∗ 1 = ε 】 = g ( n ) t ( 1 ) 【当且仅当 T=1, ε ( T ) = 1 时】 = g ( n ) ◻ 参考文献 algocode 算法博客
本页面最近更新:2025/9/13 12:05:10 ,更新历史 发现错误?想一起完善? 在 GitHub 上编辑此页! 本页面贡献者:Ir1d , StudyingFather , Enter-tainer , mgt , ShaoChenHeng , H-J-Granger , Marcythm , orzAtalod , Siyuan , sshwy , Early0v0 , Peanut-Tang , Xeonacid , countercurrent-time , ezoixx130 , hyp1231 , NachtgeistW , ranwen , GekkaSaori , ksyx , MegaOwIer , SamZhangQingChuan , Vxlimo , 383494 , AngelKitty , CCXXXI , cjsoft , diauweb , Gesrua , Great-designer , guodong2005 , Henry-ZHR , HeRaNO , iamtwz , Konano , Lcyanstars , LovelyBuggies , Luckyblock233 , Makkiy , Menci , minghu6 , mxr612 , ouuan , P-Y-Y , PotassiumWings , Suyun514 , Tiphereth-A , weiyong1024 , Chrogeek , CyaceQuious , FFjet , frank-xjh , GavinZhengOI , hehelego , hjsjhn , hydingsy , i-yyi , kenlig , kxccc , luojiny1 , lychees , nalemy , qwqAutomaton , shawlleyw , Sshwy , SukkaW , UserUnauthorized , WineChord , yjl9903 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用