筛法
前置知识
数论函数：定义在正整数上的函数。
例：1 ( n ) = 1 , i d k ( n ) = n k , 2 ( n ) = 2 1(n)=1,\operatorname{id_k}(n)=n^k,2(n)=2 1 ( n ) = 1 , i d k ( n ) = n k , 2 ( n ) = 2
若 ∀ a , b , gcd ( a , b ) = 1 ⇒ f ( a b ) = f ( a ) f ( b ) \forall a,b, \gcd(a,b)=1\Rightarrow f(ab)=f(a)f(b) ∀ a , b , g cd( a , b ) = 1 ⇒ f ( ab ) = f ( a ) f ( b ) f f f
迪利克雷卷积： 两个数论函数 f , g f,g f , g ( f ∗ g ) ( n ) = ∑ i ∣ n f ( i ) g ( n i ) (f*g)(n)=\sum \limits_{i|n}f(i) g(\frac ni) ( f ∗ g ) ( n ) = i ∣ n ∑ f ( i ) g ( i n ) f , g f,g f , g f ∗ g f*g f ∗ g
ϵ ( n ) = [ n = 1 ] ϵ ∗ f = f 1 ∗ 1 = σ 0 = ∑ i ∣ n 1 1 ∗ id k = : σ k φ ∗ 1 = id \epsilon (n)=[n=1]\\\epsilon *f=f\\1*1=\sigma_0=\sum \limits_{i|n} 1\\1*\operatorname{id}_k=: \sigma _k \\ \varphi*1=\operatorname{id} ϵ ( n ) = [ n = 1 ] ϵ ∗ f = f 1 ∗ 1 = σ 0 = i ∣ n ∑ 1 1 ∗ id k =: σ k φ ∗ 1 = id
迪利克雷逆：若 f ∗ g = ϵ f*g=\epsilon f ∗ g = ϵ g g g f f f g g g f − 1 f^{-1} f − 1
[ n = 1 ] = ∑ i ∣ n f − 1 ( i ) f ( n i ) = f ( 1 ) f − 1 ( n ) + ∑ i > 1 , i ∣ n f ( i ) f − 1 ( n i ) f − 1 ( n ) = [ n = 1 ] − ∑ i > 1 , i ∣ n f ( i ) f − 1 ( n i ) f ( 1 ) [n=1]=\sum\limits_{i|n} f^{-1}(i)f(\frac ni)=f(1)f^{-1}(n)+\sum\limits_{i>1,i|n}f(i)f^{-1}(\frac ni)\\f^{-1}(n)=\dfrac{[n=1]-\sum \limits_{i>1,i|n} f(i)f^{-1}(\frac ni)}{f(1)} [ n = 1 ] = i ∣ n ∑ f − 1 ( i ) f ( i n ) = f ( 1 ) f − 1 ( n ) + i > 1 , i ∣ n ∑ f ( i ) f − 1 ( i n ) f − 1 ( n ) = f ( 1 ) [ n = 1 ] − i > 1 , i ∣ n ∑ f ( i ) f − 1 ( i n )
于是 f f f f ( 1 ) ≠ 0 f(1)≠0 f ( 1 ) = 0
整除
[ [ n i ] j ] = [ n i j ] , ∀ i ≤ n , [ n [ n i ] ] [\frac{[\frac ni]}{j}]=[\frac n{ij}],\forall i\le n,[\frac{n}{[\frac ni]}] [ j [ i n ] ] = [ ij n ] , ∀ i ≤ n , [ [ i n ] n ] [ n x ] = [ n i ] [\frac{n}x]=[\frac ni] [ x n ] = [ i n ] x x x
记 D n = { [ n i ] ∣ i = 1 , 2 , . . . , n } , ∣ D n ∣ = O ( n ) D_n=\{[\frac ni]|i=1,2,...,n\}, |D_n|=O(\sqrt n) D n = {[ i n ] ∣ i = 1 , 2 , ... , n } , ∣ D n ∣ = O ( n )
μ ( n ) \mu(n) μ ( n ) 莫比乌斯函数 μ \mu μ 1 − 1 1^{-1} 1 − 1
若 n n n 1 1 1 μ ( n ) = 0 \mu(n)=0 μ ( n ) = 0 k k k n n n μ ( n ) = ( − 1 ) k \mu(n)=(-1)^k μ ( n ) = ( − 1 ) k
由定义，
f ( n ) = ∑ i ∣ n g ( i ) ⇔ g ( n ) = ∑ i ∣ n μ ( n i ) f ( i ) f ( n ) = ∑ n ∣ i g ( i ) ⇔ g ( n ) = ∑ n ∣ i μ ( i n ) f ( i ) f(n)=\sum \limits_{i|n}g(i)\Leftrightarrow g(n)=\sum \limits_{i|n}\mu(\frac ni) f(i)\\f(n)=\sum \limits_{n|i}g(i)\Leftrightarrow g(n)=\sum \limits_{n|i}\mu(\frac in) f(i) f ( n ) = i ∣ n ∑ g ( i ) ⇔ g ( n ) = i ∣ n ∑ μ ( i n ) f ( i ) f ( n ) = n ∣ i ∑ g ( i ) ⇔ g ( n ) = n ∣ i ∑ μ ( n i ) f ( i )
线性筛可以 O ( n ) O(n) O ( n )
例1
求 ∑ i = 1 n ∑ j = 1 m [ σ 1 ( gcd ( i , j ) ) ≤ a ] σ 1 ( gcd ( i , j ) ) , n , m ≤ 10 5 , q ≤ 2 × 10 4 \sum \limits_{i=1}^{n } \sum \limits_{j=1}^{m} [\sigma_1(\gcd(i,j)) \le a] \sigma_1(\gcd(i,j)),n,m\le 10^5,q\le 2\times 10^4 i = 1 ∑ n j = 1 ∑ m [ σ 1 ( g cd( i , j )) ≤ a ] σ 1 ( g cd( i , j )) , n , m ≤ 1 0 5 , q ≤ 2 × 1 0 4
∑ i = 1 n ∑ j = 1 m [ σ 1 ( gcd ( i , j ) ) ≤ a ] σ 1 ( gcd ( i , j ) ) = ∑ d = 1 n ∑ i = 1 n d ∑ j = 1 m d [ σ 1 ( d ) ≤ a ] [ gcd ( i , j ) = 1 ] σ 1 ( d ) = ∑ d = 1 n σ 1 ( d ) [ σ 1 ( d ) ≤ a ] ∑ i = 1 n d ∑ j = 1 m d [ gcd ( i , j ) = 1 ] = ∑ d = 1 n σ 1 ( d ) [ σ 1 ( d ) ≤ a ] ∑ i = 1 n d ∑ j = 1 m d ∑ k ∣ gcd ( i , j ) μ ( k ) = ∑ d = 1 n σ 1 ( d ) [ σ 1 ( d ) ≤ a ] ∑ k = 1 n d ⌊ n d k ⌋ ⌊ m d k ⌋ μ ( k ) \begin{align} &\sum \limits_{i=1}^{n } \sum \limits_{j=1}^{m} [\sigma_1(\gcd(i,j)) \le a] \sigma_1(\gcd(i,j))\\ &=\sum \limits_{d=1}^n \sum \limits_{i=1}^{\frac nd} \sum \limits_{j=1}^{\frac md}[\sigma_1(d)\le a][\gcd(i,j)=1] \sigma_1(d)
\\&= \sum \limits_{d=1}^n \sigma_1(d)[\sigma_1(d)\le a]\sum \limits_{i=1}^\frac nd\sum\limits_{j=1}^\frac md [\gcd(i,j)=1] \\&=
\sum \limits_{d=1}^n \sigma_1(d)[\sigma_1(d)\le a]\sum \limits_{i=1}^\frac nd\sum\limits_{j=1}^\frac md \sum \limits_{k|\gcd(i,j)}\mu(k)
\\&= \sum \limits_{d=1}^n \sigma_1(d)[\sigma_1(d)\le a]\sum \limits_{k=1}^\frac nd\lfloor \frac{n}{dk}\rfloor \lfloor \frac{m}{dk} \rfloor \mu(k)
\end{align}
i = 1 ∑ n j = 1 ∑ m [ σ 1 ( g cd( i , j )) ≤ a ] σ 1 ( g cd( i , j )) = d = 1 ∑ n i = 1 ∑ d n j = 1 ∑ d m [ σ 1 ( d ) ≤ a ] [ g cd( i , j ) = 1 ] σ 1 ( d ) = d = 1 ∑ n σ 1 ( d ) [ σ 1 ( d ) ≤ a ] i = 1 ∑ d n j = 1 ∑ d m [ g cd( i , j ) = 1 ] = d = 1 ∑ n σ 1 ( d ) [ σ 1 ( d ) ≤ a ] i = 1 ∑ d n j = 1 ∑ d m k ∣ g c d ( i , j ) ∑ μ ( k ) = d = 1 ∑ n σ 1 ( d ) [ σ 1 ( d ) ≤ a ] k = 1 ∑ d n ⌊ d k n ⌋ ⌊ d k m ⌋ μ ( k ) 设 T = d k T=dk T = d k
= ∑ T = 1 n ⌊ n T ⌋ ⌊ m T ⌋ ∑ k ∣ T μ ( k ) σ 1 ( T k ) [ σ 1 ( T k ) ≤ a ] \begin{align}&= \sum \limits_{T=1}^n \lfloor \frac{n}{T}\rfloor \lfloor \frac{m}{T} \rfloor \sum \limits_{k|T} \mu(k) \sigma_1(\frac Tk) [\sigma_1(\frac Tk)\le a] \end{align}
= T = 1 ∑ n ⌊ T n ⌋ ⌊ T m ⌋ k ∣ T ∑ μ ( k ) σ 1 ( k T ) [ σ 1 ( k T ) ≤ a ] 后面那个式子可以看为一个关于 ( T , a ) (T,a) ( T , a ) σ 1 ( x ) \sigma_1(x) σ 1 ( x ) a a a a a a σ 1 ( k ) \sigma_1(k) σ 1 ( k ) k , 2 k , 3 k , . . . k,2k,3k,... k , 2 k , 3 k , ... μ ( 1 ) σ 1 ( k ) , μ ( 2 ) σ 1 ( k ) . . . \mu(1)\sigma_1(k), \mu(2)\sigma_1(k)... μ ( 1 ) σ 1 ( k ) , μ ( 2 ) σ 1 ( k ) ... O ( n log 2 n ) O(n \log^2 n) O ( n log 2 n ) O ( T n log n ) O(T \sqrt n \log n) O ( T n log n )
# include < bits/stdc++.h > using namespace std; typedef long long ll; # define int ll const int N = 1 e 5 + 5 , M = ( 1 ll << 31 ); struct BIT { int t [N << 1 ]; int query ( int x ){ int ret = 0 ; for (;x;x -= (x &- x)){ ret += t [x];ret %= M; } return ret; } void add ( int pos , int x ){ for (;pos < N;pos += (pos &- pos)) t [pos] += x , t [pos] += M , t [pos] %= M; } }t; pair <int , int> s1 [N]; int mu [N] , p [N] , pcnt; bool isp [N]; void init (){ mu [ 1 ] = 1 ; for ( int i = 2 ;i <= N - 5 ;i ++ ){ if ( ! isp [i]) p [ ++ pcnt] = i , mu [i] =- 1 ; for ( int j = 1 ;j <= pcnt and (i * p [j]) <= N - 5 ;j ++ ){ isp [i * p [j]] = 1 ; if (i % p [j] == 0 ){ mu [i * p [j]] = 0 ; break ; } mu [i * p [j]] =- mu [i]; } } for ( int i = 1 ;i <= N - 5 ;i ++ ){ s1 [i] . second = i; for ( int j = i;j <= N - 5 ;j += i){ s1 [j] . first += i; } } // cerr<<s1[1].first<<" "<<s1[2].first<<" "<<s1[3].first<<" "<<s1[4].first<<endl; sort (s1 + 1 , s1 + 1 + 100000 ); } struct query { int n , m , a , id; bool operator <( const query & A ){ return a < A . a ;} } q [N]; int ans [N]; int T; signed main (){ cin >> T; init (); for ( int i = 1 ;i <= T;i ++ ){ cin >> q [i] . n >> q [i] . m >> q [i] . a ; q [i] . id = i; if ( q [i] . n > q [i] . m ) swap ( q [i] . n , q [i] . m ); } sort (q + 1 , q + 1 + T); int itr = 1 ; for ( int i = 1 ;i <= T;i ++ ){ while (itr <= 1 e 5 and s1 [itr] . first <= q [i] . a ){ for ( int j = s1 [itr] . second ;j <= N - 5 ;j += s1 [itr] . second ){ t . add (j , s1 [itr] . first * mu [j / s1 [itr] . second ]); } itr ++ ; } for ( int l = 1 , r;l <= q [i] . n ;l = r + 1 ){ r = min ( q [i] . n / ( q [i] . n / l) , q [i] . m / ( q [i] . m / l)); ans [ q [i] . id ] += (( q [i] . n / l) * ( q [i] . m / l) % M) * ( t . query (r) - t . query (l - 1 )) % M; ans [ q [i] . id ] %= M; } } for ( int i = 1 ;i <= T;i ++ )cout << ( ans [i] + M) % M << endl; return 0 ; } ::::
杜教筛
在一些问题中，我们想对于一个特定的 n n n ∑ i = 1 n f ( i ) \sum \limits_{i=1}^n f(i) i = 1 ∑ n f ( i ) ∑ i = 1 n ∑ j = 1 m [ gcd ( i , j ) = 1 ] \sum \limits_{i=1}^n \sum \limits_{j=1}^m [\gcd(i,j)=1] i = 1 ∑ n j = 1 ∑ m [ g cd( i , j ) = 1 ] D n ∪ D m D_n \cup D_m D n ∪ D m μ \mu μ
考虑迪利克雷卷积，设 h = f ∗ g h=f*g h = f ∗ g h h h
∑ i = 1 n h ( i ) = ∑ i = 1 n ∑ j ∣ i f ( j ) g ( j i ) = ∑ i = 1 n ∑ j = 1 [ n i ] f ( i ) g ( j ) = ∑ i = 1 n f ( i ) G ( [ n i ] ) \sum \limits_{i=1}^n h(i)=\sum \limits_{i=1}^n \sum \limits_{j|i} f(j)g(\frac ji)=\sum \limits_{i=1}^n\sum \limits_{j=1}^{[\frac ni]} f(i)g(j)\\=\sum \limits_{i=1}^nf(i)G([\frac ni])
i = 1 ∑ n h ( i ) = i = 1 ∑ n j ∣ i ∑ f ( j ) g ( i j ) = i = 1 ∑ n j = 1 ∑ [ i n ] f ( i ) g ( j ) = i = 1 ∑ n f ( i ) G ([ i n ]) 于是 G ( i ) = ∑ i = 1 n h ( i ) − ∑ i = 2 n f ( i ) G ( [ n i ] ) G(i)=\sum \limits_{i=1}^n h(i)-\sum \limits_{i=2}^n f(i)G([\frac ni]) G ( i ) = i = 1 ∑ n h ( i ) − i = 2 ∑ n f ( i ) G ([ i n ])
通过这个式子可以递归计算 g g g n n n f , h f,h f , h
进行优化后（线性筛计算前 n 2 3 n^{\frac 23} n 3 2 O ( n 2 3 ) O(n^{\frac 23}) O ( n 3 2 )
Powerful Number \text{Powerful Number} Powerful Number 杜教筛求解 f f f ∃ g , h , f ∗ g − 1 = h \exist g,h, f*g^{-1}=h ∃ g , h , f ∗ g − 1 = h g , h g,h g , h
设 n = p 1 k 1 p 2 k 2 ⋯ p m k m n=p_1^{k_1} p_2^{k_2}\cdots p_m^{k_m} n = p 1 k 1 p 2 k 2 ⋯ p m k m n n n powerful number \text{powerful number} powerful number ∀ i , k i ≥ 2 \forall i,k_i\ge 2 ∀ i , k i ≥ 2 powerful number \text{powerful number} powerful number a 2 b 3 a^2 b^3 a 2 b 3
n n n powerful number \text{powerful number} powerful number O ( n ) O(\sqrt n) O ( n )
假设我们想要求解 f f f f f f g g g p p p f ( p ) = g ( p ) f(p)=g(p) f ( p ) = g ( p ) h = f ∗ g − 1 h=f*g^{-1} h = f ∗ g − 1 h ( 1 ) g ( p ) + h ( p ) g ( 1 ) = g ( p ) + h ( p ) = f ( p ) + h ( p ) = f ( p ) h(1)g(p)+h(p)g(1)=g(p)+h(p)=f(p)+h(p)=f(p) h ( 1 ) g ( p ) + h ( p ) g ( 1 ) = g ( p ) + h ( p ) = f ( p ) + h ( p ) = f ( p ) h ( p ) = 0 h(p)=0 h ( p ) = 0 n n n powerful number \text{powerful number} powerful number h ( n ) h(n) h ( n ) 0 0 0
f = h ∗ g , f f=h*g,f f = h ∗ g , f
∑ i = 1 n f ( i ) = ∑ i = 1 n ∑ j = 1 [ n i ] h ( i ) g ( j ) = ∑ i = 1 n h ( i ) ∑ j = 1 [ n i ] g ( j ) \sum \limits_{i=1}^n f(i)=\sum \limits_{i=1}^n \sum \limits_{j=1}^{[\frac{n}{i}]} h(i)g(j)=\sum \limits_{i=1}^nh(i) \sum \limits_{j=1}^{[\frac ni]}g(j) i = 1 ∑ n f ( i ) = i = 1 ∑ n j = 1 ∑ [ i n ] h ( i ) g ( j ) = i = 1 ∑ n h ( i ) j = 1 ∑ [ i n ] g ( j ) g g g powerful number \text{powerful number} powerful number h h h h ( p c ) h(p^c) h ( p c ) f = g ∗ h ⇒ h ( p c ) = f ( p c ) − ∑ i = 1 c g ( p i ) h ( p c − i ) f=g*h\Rightarrow h(p^c)=f(p^c)-\sum \limits_{i=1}^c g(p^i)h(p^{c-i}) f = g ∗ h ⇒ h ( p c ) = f ( p c ) − i = 1 ∑ c g ( p i ) h ( p c − i ) O ( n ) O(\sqrt n) O ( n ) O ( n ln n ) O(\frac{n}{\ln n}) O ( l n n n ) ln n \ln n ln n O ( n ln n ) O(\sqrt n\ln n) O ( n ln n ) n n n powerful number \text{powerful number} powerful number
例：LOJ #6053. 简单的函数
积性函数 f ( n ) f(n) f ( n ) f ( p c ) = p xor c f(p^c)=p \operatorname{xor} c f ( p c ) = p xor c f f f n ≤ 10 10 n \le 10^{10} n ≤ 1 0 10
f ( p ) = { p + 1 ( p = 2 ) p − 1 otherwise f(p)=\begin{cases}p+1& (p=2)\\p-1 &\text{otherwise} \end{cases} f ( p ) = { p + 1 p − 1 ( p = 2 ) otherwise g ( n ) = { 3 φ ( n ) 2 ∣ n φ ( n ) otherwise g(n)=\begin{cases}3\varphi(n) & 2|n \\\varphi(n) &\text{otherwise} \end{cases} g ( n ) = { 3 φ ( n ) φ ( n ) 2∣ n otherwise
g g g
G ( n ) = ∑ i = 1 n [ i m o d 2 = 1 ] φ ( i ) + 3 ∑ i = 1 n [ i m o d 2 = 0 ] φ ( i ) = ∑ i = 1 n φ ( i ) + 2 ∑ i = 1 n 2 φ ( 2 i ) \begin{align} G(n)&=\sum \limits_{i=1}^n [i\bmod 2=1]\varphi(i) +3\sum \limits_{i=1}^n [i\bmod2=0]\varphi(i) \\ &=\sum \limits_{i=1}^n \varphi(i) +2\sum \limits_{i=1}^\frac n2 \varphi(2i) \end{align}
G ( n ) = i = 1 ∑ n [ i mod 2 = 1 ] φ ( i ) + 3 i = 1 ∑ n [ i mod 2 = 0 ] φ ( i ) = i = 1 ∑ n φ ( i ) + 2 i = 1 ∑ 2 n φ ( 2 i ) 记 S 1 ( n ) = ∑ i = 1 n φ ( i ) , S 2 ( n ) = ∑ i = 1 n φ ( 2 i ) S_1(n)=\sum\limits_{i=1}^n \varphi(i),S_2(n)=\sum \limits_{i=1}^n \varphi(2i) S 1 ( n ) = i = 1 ∑ n φ ( i ) , S 2 ( n ) = i = 1 ∑ n φ ( 2 i ) G ( n ) = S 1 ( n ) + 2 S 2 ( n 2 ) G(n)=S_1(n)+2S_2(\frac n2) G ( n ) = S 1 ( n ) + 2 S 2 ( 2 n )
当 2 ∣ n 2|n 2∣ n
S 2 ( n ) = ∑ i = 1 n φ ( 2 i ) = ∑ i = 1 n 2 ( φ ( 2 ( 2 i − 1 ) ) ) + φ ( 2 ( 2 i ) ) = ∑ i = 1 n 2 φ ( 2 i − 1 ) + 2 φ ( 2 i ) [ 1 ] = S 1 ( n ) + S 2 ( n 2 ) \begin{align}S_2(n)&= \sum \limits_{i=1}^n \varphi(2i)\\&= \sum \limits_{i=1}^\frac n2 (\varphi(2(2i-1)))+\varphi(2(2i)) \\ &=\sum \limits_{i=1}^{\frac n2} \varphi(2i-1)+2\varphi(2i) \ \ ^{[1]} \\ &=S_1(n)+S_2(\frac n2)\end{align}
S 2 ( n ) = i = 1 ∑ n φ ( 2 i ) = i = 1 ∑ 2 n ( φ ( 2 ( 2 i − 1 ))) + φ ( 2 ( 2 i )) = i = 1 ∑ 2 n φ ( 2 i − 1 ) + 2 φ ( 2 i ) [ 1 ] = S 1 ( n ) + S 2 ( 2 n ) 否则， φ ( 2 n ) = φ ( n ) \varphi(2n)=\varphi (n) φ ( 2 n ) = φ ( n ) S 2 ( n ) = S 1 ( n − 1 ) + S 2 ( n 2 ) + φ ( n ) = S 1 ( n ) + S 2 ( [ n 2 ] ) S_2(n)=S_1(n-1)+S_2(\frac n2)+\varphi(n)=S_1(n)+S_2([\frac n2]) S 2 ( n ) = S 1 ( n − 1 ) + S 2 ( 2 n ) + φ ( n ) = S 1 ( n ) + S 2 ([ 2 n ])
S 1 S_1 S 1 g g g
然后用 h ( p c ) = f ( p c ) − ∑ i = 1 c g ( p i ) h ( p c − i ) h(p^c)=f(p^c)-\sum \limits_{i=1}^c g(p^i)h(p^{c-i}) h ( p c ) = f ( p c ) − i = 1 ∑ c g ( p i ) h ( p c − i ) h h h
∑ i = 1 n f ( i ) = ∑ i = 1 n ∑ j = 1 [ n i ] h ( i ) g ( j ) = ∑ i = 1 n h ( i ) ∑ j = 1 [ n i ] g ( j ) \sum \limits_{i=1}^n f(i)=\sum \limits_{i=1}^n \sum \limits_{j=1}^{[\frac{n}{i}]} h(i)g(j)=\sum \limits_{i=1}^nh(i) \sum \limits_{j=1}^{[\frac ni]}g(j) i = 1 ∑ n f ( i ) = i = 1 ∑ n j = 1 ∑ [ i n ] h ( i ) g ( j ) = i = 1 ∑ n h ( i ) j = 1 ∑ [ i n ] g ( j )
[ 1 ] : [1]: [ 1 ] : φ ( n ) = n ∏ i = 1 k p k − 1 p k \varphi(n)= n\prod\limits_{i=1}^k \frac{p_k-1}{p_k} φ ( n ) = n i = 1 ∏ k p k p k − 1 p k p_k p k n n n
代码
Min25筛
Min25筛可以在 O ( n 3 4 log n ) O(\frac{n^{\frac{3}{4}}}{\log n}) O ( l o g n n 4 3 ) f ( p ) f(p) f ( p ) f ( p ) f(p) f ( p ) p p p f ( p c ) f(p^c) f ( p c )
我们对这个 f ( p ) f(p) f ( p )
∑ 1 ≤ i ≤ n f ( i ) = ∑ p ∈ p r i m e , p ≤ n f ( p ) + ∑ i ∉ p r i m e , i ≤ n f ( i ) \sum\limits_{1\le i\le n}f(i)=\sum \limits_{p\in prime,p\le n}f(p)+\sum \limits_{i \notin prime,i\le n}f(i)
1 ≤ i ≤ n ∑ f ( i ) = p ∈ p r im e , p ≤ n ∑ f ( p ) + i ∈ / p r im e , i ≤ n ∑ f ( i ) 枚举每个合数的最小质因子及次数：
∑ p ∈ p r i m e , p ≤ n f ( p ) + ∑ 1 ≤ p k , 1 ≤ p ≤ n f ( p k ) ∑ 1 ≤ i ≤ [ n p k ] , lp ( i ) > p f ( i ) \sum \limits_{p\in prime,p\le n}f(p)+\sum \limits_{1\le p^k,1\le p\le \sqrt n}f(p^k) \sum \limits_{1\le i\le [\frac{n}{p^k}],\operatorname{lp}(i)>p}f(i)
p ∈ p r im e , p ≤ n ∑ f ( p ) + 1 ≤ p k , 1 ≤ p ≤ n ∑ f ( p k ) 1 ≤ i ≤ [ p k n ] , lp ( i ) > p ∑ f ( i ) 其中 lp ( x ) \operatorname{lp}(x) lp ( x ) x x x
我们分成两步算上面这个式子。
1.求 ∑ p ∈ p r i m e , p ≤ n f ( p ) \sum \limits_{p\in prime,p\le n}f(p) p ∈ p r im e , p ≤ n ∑ f ( p )
记
g ( n , j ) = ∑ ( i ∈ p r i m e o r lp ( i ) > p j ) a n d i ≤ n i k g(n,j)=\sum \limits_{(i\in prime \ or \ \operatorname{lp}(i)>p_j) and \ i\le n} i^k
g ( n , j ) = ( i ∈ p r im e or lp ( i ) > p j ) an d i ≤ n ∑ i k i k i^k i k
当 p j 2 > n p_j^2>n p j 2 > n lp ( x ) = p j \operatorname{lp}(x)=p_j lp ( x ) = p j p j 2 > n p_j^2>n p j 2 > n
否则，考虑从 g ( n , j − 1 ) g(n,j-1) g ( n , j − 1 ) g ( n , j ) g(n,j) g ( n , j ) p j p_j p j
g ( n , j ) = g ( n , j − 1 ) − p j k [ g ( ⌊ n p j ⌋ , j − 1 ) − g ( p j − 1 , j − 1 ) ] g(n,j)=g(n,j-1)-p_j^k[g(\lfloor\frac{n}{p_j}\rfloor,j-1)-g(p_{j-1},j-1)]
g ( n , j ) = g ( n , j − 1 ) − p j k [ g (⌊ p j n ⌋ , j − 1 ) − g ( p j − 1 , j − 1 )] 关于 p j k [ g ( ⌊ n p j ⌋ , j − 1 ) − g ( p j − 1 , j − 1 ) ] p_j^k[g(\lfloor\frac{n}{p_j}\rfloor,j-1)-g(p_{j-1},j-1)] p j k [ g (⌊ p j n ⌋ , j − 1 ) − g ( p j − 1 , j − 1 )]
这是最小质因子恰为 p j p_j p j p j × x p_j\times x p j × x x x x lp ( x ) ≥ p j \operatorname{lp}(x)\ge p_j lp ( x ) ≥ p j ∑ x k \sum x^k ∑ x k
g ( ⌊ n p j ⌋ , j − 1 ) g(\lfloor\frac{n}{p_j}\rfloor,j-1) g (⌊ p j n ⌋ , j − 1 ) p j − 1 p_{j-1} p j − 1 k k k x x x p j p_j p j p j p_j p j g ( p j − 1 , j − 1 ) g(p_{j-1},j-1) g ( p j − 1 , j − 1 ) = g ( p j − 1 , j − 1 ) =g(p_j-1,j-1) = g ( p j − 1 , j − 1 ) p j p_j p j p j − 1 p_{j-1} p j − 1
所以我们有了 g g g
g ( n , j ) = { g ( n , j − 1 ) p j 2 > n g ( n , j − 1 ) − p j k [ g ( [ n p j ] , j − 1 ) − g ( p j − 1 , j − 1 ) ] p j 2 ≤ n g(n,j)=\left\{\begin{array}{l}g(n,j-1)& p_j^2>n\\g(n,j-1)-p_j^k[g([\frac{n}{p_j}],j-1)-g(p_j-1,j-1)] & p_j^2\leq n \end{array}\right.
g ( n , j ) = { g ( n , j − 1 ) g ( n , j − 1 ) − p j k [ g ([ p j n ] , j − 1 ) − g ( p j − 1 , j − 1 )] p j 2 > n p j 2 ≤ n g ( p j − 1 , j − 1 ) g(p_j-1,j-1) g ( p j − 1 , j − 1 ) ∑ i = 1 j − 1 p i k \sum \limits_{i=1}^{j-1}p_i^k i = 1 ∑ j − 1 p i k j ≤ O ( n ln n ) j\le O(\frac{\sqrt n}{\ln n}) j ≤ O ( l n n n )
同时根据整除点的性质（∣ D n ∣ = O ( n ) |D_n|=O(\sqrt n) ∣ D n ∣ = O ( n ) [ n p j ] [\frac{n}{p_j}] [ p j n ] g g g
在这一步之后，将 g ( n , j ) g(n,j) g ( n , j ) ∑ ( i ∈ p r i m e o r lp ( i ) > p j ) a n d i ≤ n f ( i ) \sum \limits_{(i\in prime \ or \ \operatorname{lp}(i)>p_j) and \ i\le n} f(i) ( i ∈ p r im e or lp ( i ) > p j ) an d i ≤ n ∑ f ( i )
2.求后面一部分
记
S ( n , j ) = ∑ 2 ≤ i ≤ n , lp ( i ) > p j f ( i ) S(n,j)=\sum \limits_{2\le i\le n,\operatorname{lp}(i)>p_j}f(i)
S ( n , j ) = 2 ≤ i ≤ n , lp ( i ) > p j ∑ f ( i ) 则我们的答案就是 S ( n , 0 ) S(n,0) S ( n , 0 )
可以将上式中满足条件的数分为两个部分：
大于 p j p_j p j g ( n , x ) − g ( p j − 1 , j − 1 ) g(n,x)-g(p_j-1,j-1) g ( n , x ) − g ( p j − 1 , j − 1 ) x x x p x 2 ≤ n p_x^2\le n p x 2 ≤ n x x x
大于 p j p_j p j ∑ p k e , k > j f ( p k e ) ( S ( [ n p k e ] , k ) + [ e ≠ 1 ] ) \sum \limits_{p_k^e,k>j}f(p_k^e)(S([\frac{n}{p_k^e}],k)+[e\neq 1]) p k e , k > j ∑ f ( p k e ) ( S ([ p k e n ] , k ) + [ e = 1 ])
所以有
S ( n , j ) = g ( n , x ) − g ( p j − 1 , j − 1 ) + ∑ p k e , k > j f ( p k e ) ( S ( [ n p k e ] , k ) + [ e ≠ 1 ] ) S(n,j)=g(n,x)-g(p_j-1,j-1)+\sum_{p_k^e,k>j}f(p_k^e)(S([\frac{n}{p_k^e}],k)+[e\neq 1])
S ( n , j ) = g ( n , x ) − g ( p j − 1 , j − 1 ) + p k e , k > j ∑ f ( p k e ) ( S ([ p k e n ] , k ) + [ e = 1 ]) 考虑直接爆搜。另外注意到上式不包含 f ( 1 ) f(1) f ( 1 )
例题：
SP34096 DIVCNTK
求 ∑ i = 1 n σ 0 ( i k ) \sum \limits_{i=1}^n \sigma_0(i^k) i = 1 ∑ n σ 0 ( i k )
不难发现 f ( 1 ) = 1 , f ( p ) = k + 1 , f ( p e ) = k e + 1 , f ( a b ) = f ( a ) f ( b ) f(1)=1,f(p)=k+1,f(p^e)=ke+1,f(ab)=f(a)f(b) f ( 1 ) = 1 , f ( p ) = k + 1 , f ( p e ) = k e + 1 , f ( ab ) = f ( a ) f ( b ) gcd ( a , b ) = 1 \gcd(a,b)=1 g cd( a , b ) = 1
直接做即可。
::::info[代码]
# include < bits/stdc++.h > using namespace std; typedef long long ll; # define int unsigned long long //对 2^64取模 const int N = 1 e 7 + 5 ; int p [N] , pcnt; bool isp [N]; void init ( int n ){ // p[0]=1; for ( int i = 2 ;i <= n;i ++ ){ if ( ! isp [i]){ p [ ++ pcnt] = i; // cout<<i<<endl; } for ( int j = 1 ;j <= pcnt and i * p [j] <= n;j ++ ){ isp [i * p [j]] = 1 ; if (i % p [j] == 0 ) break ; } } } int T , n , k , sqn; int g [N]; //g[i] g(第i个整除点,j)的值(其中j被压维) int d [N] , ptr; //整除点 int pos [ 3 ][N]; //d[x]的索引位置,pos[1][x]是小的（n/i）的位置 //,pos[2][x]是大的(n/i)的位置（存的是 x=n/(n/i)） int S ( int x , int y ){ //S(n,j) if ( p [y] > x) return 0 ; int posx; if (x <= sqn)posx = pos [ 1 ][x]; else posx = pos [ 2 ][n / x]; int ans = g [posx] - y * (k + 1 ); //y*(k+1)=g(p_y-1,y-1) for ( int i = y + 1 , tmp;i <= pcnt and p [i] * p [i] <= x;i ++ ){ tmp = p [i]; for ( int e = 1 ;tmp <= x;e ++ , tmp *= p [i]){ //枚举p_i^e ans += (k * e + 1 ) * S (x / tmp , i); if (e > 1 )ans += k * e + 1 ; } } return ans; } signed main (){ cin >> T; while (T -- ){ pcnt = 0 ; cin >> n >> k; sqn = sqrt (n); init (sqn);ptr = 0 ; for ( int i = 1 ;i <= n;i = n / (n / i) + 1 ){ d [ ++ ptr] = n / i; g [ptr] = n / i - 1 ; //g(n/i,0)=n/i-1（不包含f(1)） if (n / i <= sqn) pos [ 1 ][n / i] = ptr; else pos [ 2 ][n / (n / i)] = ptr; } for ( int i = 1 ;i <= pcnt;i ++ ){ // cerr<<pcnt<<" "<<ptr<<" "<<p[i]<<" "<<d[1]<<endl; for ( int j = 1 ;j <= ptr and p [i] * p [i] <= d [j];j ++ ){ //计算g(d[j],i) int itr; if ( d [j] / p [i] <= sqn)itr = pos [ 1 ][ d [j] / p [i]]; else itr = pos [ 2 ][n / ( d [j] / p [i])]; // cout<<i<<" "<<j<<" "<<itr<<endl; g [j] -= g [itr] - (i - 1 ); //f(p)=k+1,多项式和p无关（相当于0次项），不用乘p的幂 } } for ( int i = 1 ;i <= ptr;i ++ ) g [i] *= (k + 1 ); //f(p)=k+1，现在 g[x]=g(第x个整除点，n)=【<=第x个整除点的f(p)和】 // cerr<<g[1]<<" "<<g[2]<<" "<<g[3]<<" "<<g[4]<<endl; cout << S (n , 0 ) + 1 << endl; } return 0 ; } ::::
LOJ #6202 叶氏筛法
f ( p ) = p f(p)=p f ( p ) = p
LOJ #572 Misaka Network 与求和