目录

• 链接
• 描述
• 分析
• • 杜教筛
  • • 迪立克利卷积 g ∗ f g*f g∗f
    • 杜教筛
  • 建模
  • • 条件
    • 结论

链接

• HDU 5608 function - http://acm.hdu.edu.cn/showproblem.php?pid=5608

描述

• 已 知 N 2 − 3 N + 2 = ∑ d ∣ N f ( d ) ， 求 ∑ i = 1 n f ( i ) . 已知 N^2-3N+2 = \sum_{d|N}f(d)， 求\sum_{i=1}^{n}f(i). 已知N2−3N+2=∑d∣N​f(d)，求∑i=1n​f(i).

分析

杜教筛

• 迪立克利卷积 g ∗ f g*f g∗f

( g ∗ f ) ( n ) = ∑ d ∣ n g ( d ) ⋅ f ( n d ) = ∑ d ∣ n g ( n d ) ⋅ f ( d ) (g*f)(n) = \sum_{d|n}g(d)\cdot f(\frac{n}{d}) = \sum_{d|n}g(\frac{n}{d})\cdot f(d) (g∗f)(n)=d∣n∑​g(d)⋅f(dn​)=d∣n∑​g(dn​)⋅f(d)

• 杜教筛

∑ i = 1 n ( g ∗ f ) ( i ) = ∑ i = 1 n ∑ d ∣ i g ( d ) ⋅ f ( i d ) = ∑ d = 1 n g ( d ) ⋅ S ( ⌊ n d ⌋ ) \sum_{i=1}^{n}(g*f)(i)= \sum_{i=1}^{n}\sum_{d|i}g(d)\cdot f(\frac{i}{d})=\sum_{d=1}^{n}g(d)\cdot S(\lfloor\frac{n}{d}\rfloor) i=1∑n​(g∗f)(i)=i=1∑n​d∣i∑​g(d)⋅f(di​)=d=1∑n​g(d)⋅S(⌊dn​⌋)
= g ( 1 ) ⋅ S ( n ) + ∑ d = 2 n g ( d ) ⋅ S ( ⌊ n d ⌋ ) ⇒ =g(1)\cdot S(n)+\sum_{d=2}^{n}g(d)\cdot S(\lfloor\frac{n}{d} \rfloor) \Rightarrow =g(1)⋅S(n)+d=2∑n​g(d)⋅S(⌊dn​⌋)⇒
g ( 1 ) ⋅ S ( n ) = ∑ i = 1 n ( g ∗ f ) ( i ) − ∑ d = 2 n g ( d ) ⋅ S ( ⌊ n d ⌋ ) g(1)\cdot S(n)=\sum_{i=1}^{n}(g*f)(i)-\sum_{d=2}^{n}g(d)\cdot S(\lfloor\frac{n}{d} \rfloor) g(1)⋅S(n)=i=1∑n​(g∗f)(i)−d=2∑n​g(d)⋅S(⌊dn​⌋)

建模

• 条件

∑ d ∣ N f ( d ) ⋅ 1 = ( f ∗ I ) ( n ) = ( I ∗ f ) ( n ) = ∑ d ∣ N 1 ⋅ f ( n d ) ， 式 中 I ( n ) = 1 \sum_{d|N}f(d)\cdot 1 = (f*I)(n)=(I*f)(n)=\sum_{d|N}1\cdot f(\frac{n}{d}) ，式中I(n)=1 d∣N∑​f(d)⋅1=(f∗I)(n)=(I∗f)(n)=d∣N∑​1⋅f(dn​)，式中I(n)=1
即 ： N 2 − 3 N + 2 = ∑ d ∣ N 1 ⋅ f ( n d ) 即：N^2-3N+2=\sum_{d|N}1\cdot f(\frac{n}{d}) 即：N2−3N+2=d∣N∑​1⋅f(dn​)

• 结论

S ( N ) = ∑ i = 1 N ( i 2 − 3 i + 2 ) − ∑ d = 2 N 1 ⋅ S ( ⌊ N d ⌋ ) = ∑ i = 1 n ( i 2 − 3 i + 2 ) − ∑ d = 2 N S ( ⌊ N d ⌋ ) S(N) =\sum_{i =1}^{N}(i^2-3i+2)-\sum_{d=2}^{N}1\cdot S(\lfloor\frac{N}{d} \rfloor)=\sum_{i =1}^{n}(i^2-3i+2)-\sum_{d=2}^{N}S(\lfloor\frac{N}{d} \rfloor) S(N)=i=1∑N​(i2−3i+2)−d=2∑N​1⋅S(⌊dN​⌋)=i=1∑n​(i2−3i+2)−d=2∑N​S(⌊dN​⌋)