Number Theoretic Function

Number Theoretic Function

「數論函數」。數論領域的經典函數。諸如因數數量函數σ₀(n)、因數總和函數σ₁(n)、質因數數量函數ω(n)、質數數量函數π(n)、互質數量函數φ(n)、質因數排容函數μ(n)、……。維基百科整理了一份詳細列表:

https://en.wikipedia.org/wiki/Arithmetic_function

一般來說,函數輸入是正整數,函數輸出是整數。數論函數可以視作一串整數數列。

Additive Function / Multiplicative Function

數論函數通常是「加性函數」或「乘性函數」,形成遞迴公式。

additive function:       f(a + b) = f(a) × f(b)   when a ⊥ b
multiplicative function: f(a × b) = f(a) × f(b)   when a ⊥ b
加性函數:輸入相加等同輸出相乘,當輸入互質。
乘性函數:輸入相乘等同輸出相乘,當輸入互質。

更強的版本。

completely additive function:       f(a + b) = f(a) × f(b)
completely multiplicative function: f(a × b) = f(a) × f(b)
完全加性函數:輸入相加等同輸出相乘。
完全乘性函數:輸入相乘等同輸出相乘。

演算法是篩法,或者說是Dynamic Programming。

ICPC 7837

Linear Function

「加性函數」與「倍性函數」同時成立,稱作「線性函數」。

只是順便介紹一下。由於是不同領域,加性函數撞名了。

additive function:               f(a + b) = f(a) + f(b)
homogeneous function of order 1: f(k ⋅ x) = k ⋅ f(x)
加性函數:輸入相加等同輸出相加。
倍性函數:輸入倍率等同輸出倍率。(整數系統的情況下,倍率等同乘法。)

演算法是矩陣求解。

Scalar Function

「倍率函數」與「指數函數」。

只是順便介紹一下。由於是不同領域,名稱不一致了。

https://math.stackexchange.com/questions/22069/

scalar function:      f(a + b) = f(a) + f(b)  ⇔  f(x) = cx
exponential function: f(a + b) = f(a) × f(b)  ⇔  f(x) = bˣ

Coprime Counting Function

Coprime Counting Function φ(n)

1到n的正整數當中,跟n互質(最大公因數是一)的數,總共有幾個。

性質

φ(p) = p - 1                   when p is prime
φ(pⁿ) = pⁿ - pⁿ⁻¹              when p is prime
φ(a × b) = φ(a) × φ(b)         when a and b are coprime
φ(n) = φ(p₁n₁) × φ(p₂n₂) × …   when n = p₁n₁ × p₂n₂ × … is prime factorization
φ(a × b) = φ(a) × φ(b) × gcd(a,b) ÷ φ(gcd(a,b))

希臘字母φ,唸做/faɪ/,可以寫做phi。

計算一項

數學公式。不用一個一個去計算最大公因數,非常有效率!

首先是質因數分解:

n = p₁n₁ × p₂n₂ × ... × pₖnₖ   where p₁ ... pₖ are primes

以質因數計算Coprime Counting Function:

φ(n) = n × (1 - 1/p₁) × (1 - 1/p₂) × ... × (1 - 1/pₖ)

採用這個順序計算,避免溢位:

n ÷ p₁ × (p₁-1) ÷ p₂ × (p₂-1) ÷ ... ÷ pₖ × (pₖ-1)

試除法,時間複雜度O(sqrt(n))。預先建立質數表,降為O(π(sqrt(n))),其中π(n)是1到n的質數數量。預先質因數分解,降為O(ω(n)),其中ω(n)是n的質因數數量。

UVa 10299 10179 11064

計算每一項

篩法。時間複雜度O(NloglogN)。

線性篩法。時間複雜度O(N)。

首先運用線性篩法,求得每個數的最小質因數。然後運用倍性函數,實施Dynamic Programming。時間複雜度O(N)。

UVa 10820 10990 11327 11424 11426 12493

Möbius Function

Möbius Function μ(n)

質因數重複為0、不重複為±1。不重複的情況下,偶數個質因數為+1、奇數個質因數為-1。

用排容原理求一個數字的所有因數總和,就會使用此函數。

性質

μ(p¹) = -1                     when p is prime
μ(p²) = μ(p³) = ... = 0        when p is prime
μ(a × b) = μ(a) × μ(b)         when a and b are coprime
μ(n) = μ(p₁n₁) × μ(p₂n₂) × …   when n = p₁n₁ × p₂n₂ × … is prime factorization

希臘字母μ,唸做/mju:/,可以寫做mu。

計算一項

試除法,時間複雜度O(sqrt(n))。預先建立質數表,降為O(π(sqrt(n))),其中π(n)是1到n的質數數量。預先質因數分解,降為O(ω(n)),其中ω(n)是n的質因數數量。

計算每一項

線性篩法。時間複雜度O(N)。

首先運用線性篩法,求得每個數的最小質因數。然後運用倍性函數,實施Dynamic Programming。時間複雜度O(N)。

ICPC 2116 luogu P4318

Divisor Function

Divisor Counting Function σ₀(n)

n的因數數量。

Divisor Sum Function σ₁(n)

n的因數總和。

Divisor Function σₖ(n)

n的因數k次方和。k=0得到因數數量,k=1得到因數總和。

性質

σ₀(p) = 2                         when p is prime
σ₀(pⁿ) = n + 1                    when p is prime
σ₀(a × b) = σ₀(a) × σ₀(b)         when a and b are coprime
σ₀(n) = σ₀(p₁n₁) × σ₀(p₂n₂) × …   when n = p₁n₁ × p₂n₂ × … is prime factorization

希臘字母σ,唸做/ˈ sɪɡmə/,可以寫做sigma。

計算一項

試除法,時間複雜度為O(sqrt(n))。預先建立質數表,降為O(π(sqrt(n))),其中π(n)是1到n的質數數量。

數學公式:質因數分解。時間複雜度依舊,但是執行時間更短。

平方根改成立方根。時間複雜度O(n)。

計算每一項

篩法。時間複雜度O(NlogN)。

Summatory Divisor Function Dₖ(n)

Divisor Function前綴和。前綴和與相鄰差互為反運算!

計算一項

時間複雜度O(sqrt(n))。

D0(n) = floor(n/1) + floor(n/2) + ... + floor(n/n)

時間複雜度O(sqrt(sqrt(n))) = O(n¼)。

D0(n) = (floor(n/1) + ... + floor(n/r)) × 2 - r²
where r = floor(sqrt(n))

luogu P2424 P6028

GCD Function

Coprime Counting Function

f(n)   =   ∑   [gcd(i,n) = 1]   Coprime Counting Function
         1≤i≤n                  Euler's Totient Function

f(n)   =   ∑   [gcd(i,j) = 1]   Coprime Triangular Counting Function
        1≤i<j≤n

f(n,m) =   ∑   [gcd(i,j) = 1]   Coprime Double Counting Function
         1≤i≤n
         1≤j≤m

預處理O(n)、計算一項O(1)。只能處理n = m的情況。

預處理O(n)、計算一項O(sqrt(n))。

沒有預處理、計算一項O(n log(n))。

luogu P2158

GCD Distribution Function

f(d;n)   =   ∑   [gcd(i,n) = d]   GCD Distribution Function
           1≤i≤n

f(d;n)   =   ∑   [gcd(i,j) = d]   GCD Triangular Distribution Function
          1≤i<j≤n

f(d;n,m) =   ∑   [gcd(i,j) = d]   GCD Double Distribution Function
           1≤i≤n
           1≤j≤m

luogu P4450 P2522 P2568 P2257 P3172

GCD Sum Function

F(n)   =   ∑   gcd(i,n)   GCD Sum Function
         1≤i≤n            Pillai's Arithmetical Function

F(n)   =   ∑   gcd(i,j)   GCD Triangular Sum Function
        1≤i<j≤n

F(n,m) =   ∑   gcd(i,j)   GCD Double Sum Function
         1≤i≤n
         1≤j≤m

預處理O(n)、計算一項O(sqrt(n))。

沒有預處理、計算一項O(n log(n))。

UVa 11417 11424 11426 luogu P1390 P2398 P3768

Prime Counting Function

Prime Counting Function π(n)

https://min-25.hatenablog.com/entry/2018/11/11/172216

luogu P5493