前情提要：有狗狗（迫真）模拟赛里放这个东西的板子（？）题，这下只能被迫学习了。
定义一个数是 Powerful Number，当且仅当其的所有质因子次幂都至少为二，简称 PN。
光是这个不够，还有一个关键结论：所有 PN 都可以写成 a 2 b 3 a^2b^3 a 2 b 3
这是简单的，考虑对于任意一个不小于等于二的数都可以写成 2 x + 3 y 2x+3y 2 x + 3 y
有这个可以证明什么？
考虑粗略估计 n n n
∑ i = 2 n ⌊ n i 2 3 ⌋ \sum_{i=2}^{\sqrt{n}} \big\lfloor \sqrt[3]{\frac{n}{i^2}}\big\rfloor
i = 2 ∑ n ⌊ 3 i 2 n ⌋
把求和符号换成积分可以得到数量级是 O ( n ) \mathcal{O}(\sqrt{n}) O ( n )
（说实话我也不清楚这里常数有多少，感觉这实在有点太粗略了，但是下界又刚好是 n \sqrt{n} n
这样可以通过线筛处理 n \sqrt{n} n n n n O ( n ) \mathcal{O}(\sqrt{n}) O ( n )
这得到了什么？
如果我们有一个积性函数 f f f ∀ p ∈ P , f ( p ) = 0 \forall p\in \mathbb{P},f(p)=0 ∀ p ∈ P , f ( p ) = 0 f f f O ( n ) \mathcal{O}(\sqrt{n}) O ( n ) n n n f f f
求积性函数 f f f
我们构造一个积性函数 f ′ f' f ′ ∀ p ∈ P , f ′ ( p ) = f ( p ) \forall p\in \mathbb{P},f'(p)=f(p) ∀ p ∈ P , f ′ ( p ) = f ( p )
然后找出一个积性函数 g g g f ′ ∗ g = f f'*g=f f ′ ∗ g = f
注意到对于 ∀ p ∈ P \forall{p}\in \mathbb P ∀ p ∈ P f ( p ) = f ′ ( p ) g ( 1 ) + f ′ ( 1 ) g ( p ) f(p)=f'(p)g(1)+f'(1)g(p) f ( p ) = f ′ ( p ) g ( 1 ) + f ′ ( 1 ) g ( p ) f ( p ) = f ′ ( p ) = f ′ ( p ) g ( 1 ) , f ′ ( 1 ) = 1 f(p)=f'(p)=f'(p)g(1),f'(1)=1 f ( p ) = f ′ ( p ) = f ′ ( p ) g ( 1 ) , f ′ ( 1 ) = 1 g ( p ) = 0 g(p)=0 g ( p ) = 0 g g g
然后剩下就是简单的了：
∑ i = 1 n f ( i ) = ∑ x y ≤ n g ( x ) f ′ ( y ) \sum_{i=1}^{n}f(i)=\sum_{xy\leq n}g(x)f'(y)
i = 1 ∑ n f ( i ) = x y ≤ n ∑ g ( x ) f ′ ( y )
枚举所有 PN 位置的 x x x f ′ f' f ′ ⌊ n x ⌋ \bigg\lfloor\dfrac{n}{x}\bigg\rfloor ⌊ x n ⌋
如果 f ′ f' f ′ i d \mathrm{id} i d O ( 1 ) \mathcal{O}(1) O ( 1 ) O ( n ) \mathcal{O}(\sqrt{n}) O ( n )
否则可能需要对 f ′ f' f ′ f ′ f' f ′ f ′ f' f ′ f ′ ( n ) f'(n) f ′ ( n ) O ( n 2 3 ) \mathcal{O}(n^{\frac{2}{3}}) O ( n 3 2 )
还没完，这里 g g g
如果能够直接蒙出定义式是最好的，否则考虑利用 f ( p k ) = ∑ i = 0 k f ′ ( p i ) g ( p k − i ) f(p^k)=\sum_{i=0}^kf'(p^i)g(p^{k-i}) f ( p k ) = ∑ i = 0 k f ′ ( p i ) g ( p k − i ) k k k
核心思想是将求和位置拆成素数，合数和 1 1 1
要求 f f f
考虑计算 f f f f f f
我们记 p k p_k p k k k k p 0 = 1 p_0=1 p 0 = 1 F ( n , k ) F(n,k) F ( n , k ) ( 1 , n ] (1,n] ( 1 , n ] p k p_k p k f f f
可以得到转移式：
F ( n , k ) = G ( n ) − G ( p k ) + ∑ i > k ∑ j > 0 f ( p i j ) × ( F ( ⌊ n p i j ⌋ , i ) + [ j > 1 ] ) F(n,k)=G(n)-G(p_k)+\sum_{i>k}\sum_{j>0} f(p_i^j)\times \bigg(F(\big\lfloor\dfrac{n}{p_i^j}\big\rfloor,i)+[j>1]\bigg)
F ( n , k ) = G ( n ) − G ( p k ) + i > k ∑ j > 0 ∑ f ( p i j ) × ( F ( ⌊ p i j n ⌋ , i ) + [ j > 1 ] )
G ( n ) G(n) G ( n ) f f f n n n
转移的意义相当于先把大于 p k p_k p k p k p_k p k
注意这里 j > 1 j>1 j > 1 F ( n , k ) F(n,k) F ( n , k ) f ( 1 ) f(1) f ( 1 ) j > 1 j>1 j > 1 p i j p_i^j p i j j = 1 j=1 j = 1 p i p_i p i
最后 F ( n , 0 ) + f ( 1 ) F(n,0)+f(1) F ( n , 0 ) + f ( 1 )
假如我们可以 O ( 1 ) O(1) O ( 1 ) G G G O ( n 1 − ϵ ) O(n^{1-\epsilon}) O ( n 1 − ϵ ) O ( n 3 4 log n ) O\bigg(\dfrac{n^{\frac{3}{4}}}{\log n}\bigg) O ( log n n 4 3 )
考虑把 G ( n ) G(n) G ( n )
我们可以构造一个完全积性函数 f ′ f' f ′ ，满足 f ′ ( p ) = f ( p ) f'(p)=f(p) f ′ ( p ) = f ( p ) G ′ ( n , k ) G'(n,k) G ′ ( n , k ) ( 1 , n ] (1,n] ( 1 , n ] 大于 p k p_k p k G ( n ) = G ′ ( n , + inf ) G(n)=G'(n,+\inf) G ( n ) = G ′ ( n , + inf )
考虑按照 k k k
如果 p k 2 > n p_k^2>n p k 2 > n G ′ ( n , k ) = G ′ ( n , k − 1 ) G'(n,k)=G'(n,k-1) G ′ ( n , k ) = G ′ ( n , k − 1 ) p k p_k p k
否则提出一个 f ′ ( k ) f'(k) f ′ ( k ) G ′ ( n , k ) = G ′ ( n , k − 1 ) − f ′ ( k ) ( G ′ ( n p k , k − 1 ) − G ′ ( p k − 1 , k − 1 ) ) G'(n,k)=G'(n,k-1)-f'(k)(G'(\frac{n}{p_k},k-1)-G'(p_k-1,k-1)) G ′ ( n , k ) = G ′ ( n , k − 1 ) − f ′ ( k ) ( G ′ ( p k n , k − 1 ) − G ′ ( p k − 1 , k − 1 ) )
最后那一项是因为 G ′ G' G ′ f ′ ( k ) f'(k) f ′ ( k ) p k p_k p k
这里因为 p k 2 ≤ n p_k^2\leq n p k 2 ≤ n G ′ ( p k − 1 , k − 1 ) G'(p_k-1,k-1) G ′ ( p k − 1 , k − 1 )
因为 k k k p k 2 > n p_k^2>n p k 2 > n G G G G ′ G' G ′ p k 2 < n p_k^2<n p k 2 < n n n n n n n G ′ G' G ′ O ( n 3 4 log n ) O\bigg(\dfrac{n^{\frac{3}{4}}}{\log n}\bigg) O ( log n n 4 3 )
现在问题是 G ′ ( n , 0 ) G'(n,0) G ′ ( n , 0 )
如果 f ′ f' f ′
不过 Min 25 筛最大的优势在于，因为计算 G G G f f f f ′ f' f ′
还有一个很奇妙的是，G G G f ′ = 1 f'=1 f ′ = 1
定义积性函数 f ( x ) f(x) f ( x ) f ( p k ) = p k ( p k − 1 ) f(p ^ k) = p ^ k(p ^ k - 1) f ( p k ) = p k ( p k − 1 ) p p p
∑ i = 1 n f ( i ) \sum_{i = 1} ^ n f(i)
i = 1 ∑ n f ( i )
对 1 0 9 + 7 10 ^ 9 + 7 1 0 9 + 7
Min 25 的话，注意到质数处的取值相当于 f ( p ) = p 2 − p f(p)=p^2-p f ( p ) = p 2 − p f ′ f' f ′ p 2 p^2 p 2 p p p G G G
还可以 PN，注意到质数处的取值相当于 f ′ ( p ) = i d ( p ) φ ( p ) f'(p)=\mathrm{id}(p)\varphi(p) f ′ ( p ) = i d ( p ) φ ( p ) i d \mathrm{id} i d i d 2 \mathrm{id}_2 i d 2 f ′ f' f ′
这里还有一个类似的结论是：
若 f ( p ) = i d k ( p ) φ ( p ) f(p)=\mathrm{id}_{k}(p)\varphi(p) f ( p ) = i d k ( p ) φ ( p ) f ( p ) ∗ i d k = i d k + 1 f(p)*\mathrm{id}_{k}=\mathrm{id}_{k+1} f ( p ) ∗ i d k = i d k + 1
或者说如果是 i d \mathrm{id} i d i d \mathrm{id} i d n k n^k n k
比如 f ( p ) = i d k μ ( p ) , g ( p ) = i d k + 1 ( p ) f(p)=\mathrm{id}_k\mu(p),g(p)=\mathrm{id}_{k+1}(p) f ( p ) = i d k μ ( p ) , g ( p ) = i d k + 1 ( p ) f ∗ g = i d k f*g=\mathrm{id}_{k} f ∗ g = i d k
进一步地发现这相当于是点积的一个特殊分配律：
( f ⋅ g ) ∗ ( f ⋅ h ) = f ⋅ ( g ∗ h ) (f\cdot g)*(f \cdot h)=f \cdot (g*h)
( f ⋅ g ) ∗ ( f ⋅ h ) = f ⋅ ( g ∗ h )
要求 f f f g , h g,h g , h
这对于找杜教筛函数可能比较有用。
