Möbius
莫比乌斯函数
定义
μ ( n ) = { 1 n = 1 0 n 含有平方因子 ( − 1 ) k k 为本质不同的质因子个数 \mu(n)=
\begin{cases}
1 &n=1 \\
0 &n含有平方因子 \\
(-1)^k &k为本质不同的质因子个数
\end{cases} μ ( n ) = ⎩ ⎨ ⎧ 1 0 ( − 1 ) k n = 1 n 含有平方因子 k 为本质不同的质因子个数 性质
莫比乌斯函数是积性函数，且有
∑ d ∣ n μ ( d ) = { 1 n = 1 0 n ≠ 1 \sum\limits_{d|n}\mu(d)=
\begin{cases}
1 &n=1\\
0 &n\neq 1\\
\end{cases} d ∣ n ∑ μ ( d ) = { 1 0 n = 1 n = 1 即∑ d ∣ n μ ( d ) = ε ( n ) \sum\limits_{d|n}\mu(d)=\varepsilon(n) d ∣ n ∑ μ ( d ) = ε ( n ) μ ∗ 1 = ε \mu*1=\varepsilon μ ∗ 1 = ε
证明
设n = ∏ i = 1 k p i c i ， n ′ = ∏ i = 1 k p i n=\prod\limits_{i=1}^{k}p_i^{c_i}，n'=\prod\limits_{i=1}^{k}p_i n = i = 1 ∏ k p i c i ， n ′ = i = 1 ∏ k p i ∑ d ∣ n μ ( d ) = ∑ d ∣ n ′ μ ( d ) = ∑ i = 0 k C k i ( − 1 ) i \sum\limits_{d|n}\mu(d)=\sum\limits_{d|n'}\mu(d)=\sum\limits_{i=0}^{k}C_k^i(-1)^i d ∣ n ∑ μ ( d ) = d ∣ n ′ ∑ μ ( d ) = i = 0 ∑ k C k i ( − 1 ) i ∑ i = 0 k C k i ( − 1 ) i 1 k − i = ( 1 − 1 ) k \sum\limits_{i=0}^{k}C_k^i(-1)^i1^{k-i}=(1-1)^k i = 0 ∑ k C k i ( − 1 ) i 1 k − i = ( 1 − 1 ) k k = 0 ( n = 1 ) k=0(n=1) k = 0 ( n = 1 )
莫比乌斯变换
公式
1.若f ( n ) = ∑ d ∣ n g ( d ) f(n)=\sum\limits_{d|n}g(d) f ( n ) = d ∣ n ∑ g ( d ) g ( n ) = ∑ d ∣ n μ ( d ) f ( n d ) g(n)=\sum\limits_{d|n}\mu(d)f(\frac{n}{d}) g ( n ) = d ∣ n ∑ μ ( d ) f ( d n )
2.若f ( n ) = ∑ n ∣ d g ( d ) f(n)=\sum\limits_{n|d}g(d) f ( n ) = n ∣ d ∑ g ( d ) g ( n ) = ∑ n ∣ d μ ( d ) f ( d n ) g(n)=\sum\limits_{n|d}\mu(d)f(\frac{d}{n}) g ( n ) = n ∣ d ∑ μ ( d ) f ( n d )
证明
1.∑ d ∣ n μ ( d ) f ( n d ) = ∑ d ∣ n μ ( d ) ∑ k ∣ n d g ( k ) = ∑ k ∣ n g ( k ) ∑ d ∣ n k μ ( d ) = ∑ k ∣ n g ( k ) ε ( n k ) = g ( n ) \sum\limits_{d|n}\mu(d)f(\frac{n}{d})=\sum\limits_{d|n}\mu(d)\sum\limits_{k|\frac{n}{d}}g(k)=\sum\limits_{k|n}g(k)\sum\limits_{d|\frac{n}{k}}\mu(d)=\sum\limits_{k|n}g(k)\varepsilon(\frac{n}{k})=g(n) d ∣ n ∑ μ ( d ) f ( d n ) = d ∣ n ∑ μ ( d ) k ∣ d n ∑ g ( k ) = k ∣ n ∑ g ( k ) d ∣ k n ∑ μ ( d ) = k ∣ n ∑ g ( k ) ε ( k n ) = g ( n )
2.∑ n ∣ d μ ( d ) f ( d n ) = ∑ k = 1 + ∞ μ ( k n ) f ( k ) = ∑ k = 1 + ∞ μ ( k n ) ∑ k ∣ d g ( d ) = ∑ n ∣ d g ( d ) ∑ k n ∣ d μ ( k n ) = ∑ n ∣ d g ( d ) ∑ k ∣ d n μ ( k ) = ∑ n ∣ d g ( d ) ε ( d n ) = g ( n ) \sum\limits_{n|d}\mu(d)f(\frac{d}{n})=\sum\limits_{k=1}^{+\infty}\mu(kn)f(k)=\sum\limits_{k=1}^{+\infty}\mu(kn)\sum\limits_{k|d}g(d)=\sum\limits_{n|d}g(d)\sum\limits_{kn|d}\mu(kn)=\sum\limits_{n|d}g(d)\sum\limits_{k|\frac{d}{n}}\mu(k)=\sum\limits_{n|d}g(d)\varepsilon(\frac{d}{n})=g(n) n ∣ d ∑ μ ( d ) f ( n d ) = k = 1 ∑ + ∞ μ ( k n ) f ( k ) = k = 1 ∑ + ∞ μ ( k n ) k ∣ d ∑ g ( d ) = n ∣ d ∑ g ( d ) k n ∣ d ∑ μ ( k n ) = n ∣ d ∑ g ( d ) k ∣ n d ∑ μ ( k ) = n ∣ d ∑ g ( d ) ε ( n d ) = g ( n )
常用套路（例题+解释）
[ gcd ( i , j ) = = 1 ] = ε ( gcd ( i , j ) ) = ∑ d ∣ gcd ( i , j ) μ ( d ) [\gcd(i, j) == 1]=\varepsilon(\gcd(i,j))=\sum\limits_{d|\gcd(i, j)}\mu(d) [ g cd( i , j ) == 1 ] = ε ( g cd( i , j )) = d ∣ g c d ( i , j ) ∑ μ ( d )
∑ i = 1 n ∑ j = 1 m [ gcd ( i , j ) = = k ] \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\gcd(i,j)==k] i = 1 ∑ n j = 1 ∑ m [ g cd( i , j ) == k ]
题目链接：YY的GCD 、[HAOI2011]Problem b 、[POI2007]ZAP-Queries
∑ i = 1 n ∑ j = 1 m [ gcd ( i , j ) = = k ] = ∑ i = 1 ⌊ n k ⌋ ∑ j = 1 ⌊ m k ⌋ [ gcd ( i , j ) = = 1 ] = ∑ i = 1 ⌊ n k ⌋ ∑ j = 1 ⌊ m k ⌋ ∑ d ∣ gcd ( i , j ) μ ( d ) = ∑ d = 1 n μ ( d ) ∑ i = 1 ⌊ n k d ⌋ ∑ j = 1 ⌊ m k d ⌋ = ∑ d = 1 n μ ( d ) ⌊ n k d ⌋ ⌊ m k d ⌋ \begin{aligned}
\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\gcd(i,j)==k]
&= \sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}[\gcd(i,j)==1] \\
&=\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}\sum\limits_{d|\gcd(i, j)}\mu(d) \\
&=\sum\limits_{d=1}^{n}\mu(d)\sum\limits_{i=1}^{\lfloor\frac{n}{kd}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{kd}\rfloor} \\
&=\sum\limits_{d=1}^{n}\mu(d)\lfloor\frac{n}{kd}\rfloor\lfloor\frac{m}{kd}\rfloor \\
\end{aligned} i = 1 ∑ n j = 1 ∑ m [ g cd( i , j ) == k ] = i = 1 ∑ ⌊ k n ⌋ j = 1 ∑ ⌊ k m ⌋ [ g cd( i , j ) == 1 ] = i = 1 ∑ ⌊ k n ⌋ j = 1 ∑ ⌊ k m ⌋ d ∣ g c d ( i , j ) ∑ μ ( d ) = d = 1 ∑ n μ ( d ) i = 1 ∑ ⌊ k d n ⌋ j = 1 ∑ ⌊ k d m ⌋ = d = 1 ∑ n μ ( d ) ⌊ k d n ⌋ ⌊ k d m ⌋
∑ i = 1 n ∑ j = 1 m gcd ( i , j ) \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\gcd(i,j) i = 1 ∑ n j = 1 ∑ m g cd( i , j )
∑ i = 1 n ∑ j = 1 m gcd ( i , j ) = ∑ k = 1 n k ∑ i = 1 n ∑ j = 1 m [ gcd ( i , j ) = = k ] = ∑ k = 1 n k ∑ i = 1 ⌊ n k ⌋ ∑ j = 1 ⌊ m k ⌋ [ gcd ( i , j ) = = 1 ] = ∑ k = 1 n k ∑ i = 1 ⌊ n k ⌋ ∑ j = 1 ⌊ m k ⌋ ∑ d ∣ gcd ( i , j ) μ ( d ) = ∑ k = 1 n k ∑ d = 1 n μ ( d ) ∑ i = 1 , d ∣ i ⌊ n k ⌋ ∑ j = 1 , d ∣ j ⌊ m k ⌋ = ∑ k = 1 n k ∑ d = 1 n μ ( d ) ∑ i = 1 ⌊ n k d ⌋ ∑ j = 1 ⌊ m k d ⌋ = ∑ k = 1 n ∑ d = 1 n k μ ( d ) ⌊ n k d ⌋ ⌊ m k d ⌋ 令 t = k d ，原式 = ∑ t = 1 n ∑ d ∣ t μ ( d ) ( t d ) ⌊ n t ⌋ ⌊ m t ⌋ \begin{aligned}
\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\gcd(i,j)
&=\sum\limits_{k=1}^{n}k\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\gcd(i, j)==k] \\
&=\sum\limits_{k=1}^{n}k\sum\limits_{i=1}^{\lfloor \frac{n}{k} \rfloor}\sum\limits_{j=1}^{\lfloor \frac{m}{k} \rfloor}[\gcd(i, j)==1] \\
&=\sum\limits_{k=1}^{n}k\sum\limits_{i=1}^{\lfloor \frac{n}{k} \rfloor}\sum\limits_{j=1}^{\lfloor \frac{m}{k} \rfloor}\sum\limits_{d|\gcd(i, j)}\mu(d) \\
&=\sum\limits_{k=1}^{n}k\sum\limits_{d=1}^{n}\mu(d)\sum\limits_{i=1, d|i}^{\lfloor \frac{n}{k} \rfloor}\sum\limits_{j=1, d|j}^{\lfloor \frac{m}{k} \rfloor} \\
&=\sum\limits_{k=1}^{n}k\sum\limits_{d=1}^{n}\mu(d)\sum\limits_{i=1}^{\lfloor \frac{n}{kd} \rfloor}\sum\limits_{j=1}^{\lfloor \frac{m}{kd} \rfloor} \\
&=\sum\limits_{k=1}^{n}\sum\limits_{d=1}^{n}k\mu(d)\lfloor \frac{n}{kd} \rfloor\lfloor \frac{m}{kd} \rfloor \\
令t=kd，原式&=\sum\limits_{t=1}^{n}\sum\limits_{d|t}\mu(d)(\frac{t}{d})\lfloor \frac{n}{t} \rfloor\lfloor \frac{m}{t} \rfloor \\
\end{aligned} i = 1 ∑ n j = 1 ∑ m g cd( i , j ) 令 t = k d ，原式 = k = 1 ∑ n k i = 1 ∑ n j = 1 ∑ m [ g cd( i , j ) == k ] = k = 1 ∑ n k i = 1 ∑ ⌊ k n ⌋ j = 1 ∑ ⌊ k m ⌋ [ g cd( i , j ) == 1 ] = k = 1 ∑ n k i = 1 ∑ ⌊ k n ⌋ j = 1 ∑ ⌊ k m ⌋ d ∣ g c d ( i , j ) ∑ μ ( d ) = k = 1 ∑ n k d = 1 ∑ n μ ( d ) i = 1 , d ∣ i ∑ ⌊ k n ⌋ j = 1 , d ∣ j ∑ ⌊ k m ⌋ = k = 1 ∑ n k d = 1 ∑ n μ ( d ) i = 1 ∑ ⌊ k d n ⌋ j = 1 ∑ ⌊ k d m ⌋ = k = 1 ∑ n d = 1 ∑ n k μ ( d ) ⌊ k d n ⌋ ⌊ k d m ⌋ = t = 1 ∑ n d ∣ t ∑ μ ( d ) ( d t ) ⌊ t n ⌋ ⌊ t m ⌋ 定义f ( t ) = ∑ d ∣ t μ ( d ) ( t d ) f(t)=\sum\limits_{d|t}\mu(d)(\frac{t}{d}) f ( t ) = d ∣ t ∑ μ ( d ) ( d t )
原式 = ∑ t = 1 n f ( t ) ⌊ n t ⌋ ⌊ m t ⌋ 原式=\sum\limits_{t=1}^{n}f(t)\lfloor \frac{n}{t} \rfloor\lfloor \frac{m}{t} \rfloor 原式 = t = 1 ∑ n f ( t ) ⌊ t n ⌋ ⌊ t m ⌋
∑ i = 1 n ∑ j = 1 m l c m ( i , j ) \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}lcm(i,j) i = 1 ∑ n j = 1 ∑ m l c m ( i , j )
题目链接：[国家集训队]Crash的数字表格/JZPTAB
∑ i = 1 n ∑ j = 1 m l c m ( i , j ) = ∑ i = 1 n ∑ j = 1 m i j gcd ( i , j ) = ∑ k = 1 n ∑ i = 1 n ∑ j = 1 m i j k [ gcd ( i , j ) = = k ] = ∑ k = 1 n ∑ i = 1 ⌊ n k ⌋ ∑ j = 1 ⌊ m k ⌋ i j k 2 k [ gcd ( i , j ) = = 1 ] = ∑ k = 1 n k ∑ i = 1 ⌊ n k ⌋ ∑ j = 1 ⌊ m k ⌋ i j ∑ d ∣ gcd ( i , j ) μ ( d ) = ∑ k = 1 n ∑ d = 1 n k μ ( d ) d 2 ∑ i = 1 ⌊ n k d ⌋ ∑ j = 1 ⌊ m k d ⌋ i j 令 t = k d ，原式 = ∑ t = 1 n t ∑ d ∣ t d μ ( d ) ∑ i = 1 ⌊ n t ⌋ i ∑ j = 1 ⌊ m t ⌋ j \begin{aligned}
\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}lcm(i,j)
&=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\frac{ij}{\gcd(i,j)} \\
&=\sum\limits_{k=1}^{n}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\frac{ij}{k}[\gcd(i,j)==k] \\
&=\sum\limits_{k=1}^{n}\sum\limits_{i=1}^{\lfloor \frac{n}{k} \rfloor}\sum\limits_{j=1}^{\lfloor \frac{m}{k} \rfloor}\frac{ijk^2}{k}[\gcd(i,j)==1] \\
&=\sum\limits_{k=1}^{n}k\sum\limits_{i=1}^{\lfloor \frac{n}{k} \rfloor}\sum\limits_{j=1}^{\lfloor \frac{m}{k} \rfloor}ij\sum\limits_{d|\gcd(i, j)}\mu(d) \\
&=\sum\limits_{k=1}^{n}\sum\limits_{d=1}^{n}k\mu(d)d^2\sum\limits_{i=1}^{\lfloor \frac{n}{kd} \rfloor}\sum\limits_{j=1}^{\lfloor \frac{m}{kd} \rfloor}ij \\
令t=kd，原式&=\sum\limits_{t=1}^{n}t\sum\limits_{d|t}d\mu(d)\sum\limits_{i=1}^{\lfloor \frac{n}{t} \rfloor}i\sum\limits_{j=1}^{\lfloor \frac{m}{t} \rfloor}j \\
\end{aligned} i = 1 ∑ n j = 1 ∑ m l c m ( i , j ) 令 t = k d ，原式 = i = 1 ∑ n j = 1 ∑ m g cd( i , j ) ij = k = 1 ∑ n i = 1 ∑ n j = 1 ∑ m k ij [ g cd( i , j ) == k ] = k = 1 ∑ n i = 1 ∑ ⌊ k n ⌋ j = 1 ∑ ⌊ k m ⌋ k ij k 2 [ g cd( i , j ) == 1 ] = k = 1 ∑ n k i = 1 ∑ ⌊ k n ⌋ j = 1 ∑ ⌊ k m ⌋ ij d ∣ g c d ( i , j ) ∑ μ ( d ) = k = 1 ∑ n d = 1 ∑ n k μ ( d ) d 2 i = 1 ∑ ⌊ k d n ⌋ j = 1 ∑ ⌊ k d m ⌋ ij = t = 1 ∑ n t d ∣ t ∑ d μ ( d ) i = 1 ∑ ⌊ t n ⌋ i j = 1 ∑ ⌊ t m ⌋ j 定义f ( t ) = ∑ d ∣ t d μ ( d ) ， g ( n ) = ∑ i = 1 n i f(t)=\sum\limits_{d|t}d\mu(d)，g(n)=\sum\limits_{i=1}^{n}i f ( t ) = d ∣ t ∑ d μ ( d ) ， g ( n ) = i = 1 ∑ n i f f f g g g
原式 = ∑ t = 1 n t f ( t ) g ( ⌊ n t ⌋ ) g ( ⌊ m t ⌋ ) 原式=\sum\limits_{t=1}^{n}tf(t)g(\lfloor \frac{n}{t} \rfloor)g(\lfloor \frac{m}{t} \rfloor) 原式 = t = 1 ∑ n t f ( t ) g (⌊ t n ⌋) g (⌊ t m ⌋)
∑ i = 1 n ∑ j = 1 m d ( i j ) \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}d(ij) i = 1 ∑ n j = 1 ∑ m d ( ij ) d d d
题目链接：[SDOI2015]约数个数和
非常重要的性质：d ( i j ) = ∑ x ∣ i ∑ y ∣ j [ gcd ( x , y ) = = 1 ] d(ij)=\sum\limits_{x|i}\sum\limits_{y|j}[\gcd(x,y)==1] d ( ij ) = x ∣ i ∑ y ∣ j ∑ [ g cd( x , y ) == 1 ]
证明：考虑d d d d ( n ) = ∏ p = 1 k ( c p + 1 ) = ∑ p ∣ n d(n)=\prod\limits_{p=1}^{k}(c_p+1)=\sum\limits_{p|n}\quad d ( n ) = p = 1 ∏ k ( c p + 1 ) = p ∣ n ∑ p p p i i i a a a p p p j j j b b b p p p p p p ( a + b + 1 ) (a+b+1) ( a + b + 1 ) x 、 y x、y x 、 y p p p i i i p p p j j j p p p a a a j j j p p p i i i p p p b b b i 、 j i、j i 、 j p p p 1 1 1 p p p ( a + b + 1 ) (a+b+1) ( a + b + 1 ) a a a p p p i i i j j j （目前貌似无法用严格的数学公式推导，所以只能通过逻辑感性理解了。）
有了性质，我们就可以大力推式子了！！
∑ i = 1 n ∑ j = 1 m d ( i j ) = ∑ i = 1 n ∑ j = 1 m ∑ x ∣ i ∑ y ∣ j [ gcd ( x , y ) = = 1 ] = ∑ x = 1 n ∑ y = 1 m [ gcd ( x , y ) = = 1 ] ∑ i = 1 ⌊ n x ⌋ ∑ j = 1 ⌊ m y ⌋ = ∑ d = 1 n μ ( d ) ∑ x = 1 ⌊ n d ⌋ ∑ y = 1 ⌊ m d ⌋ ⌊ n x d ⌋ ⌊ m y d ⌋ = ∑ d = 1 n μ ( d ) ∑ x = 1 ⌊ n d ⌋ ⌊ n x d ⌋ ∑ y = 1 ⌊ m d ⌋ ⌊ m y d ⌋ \begin{aligned}
\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}d(ij)
&=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum\limits_{x|i}\sum\limits_{y|j}[\gcd(x,y)==1] \\
&=\sum\limits_{x=1}^{n}\sum\limits_{y=1}^{m}[\gcd(x,y)==1]\sum\limits_{i=1}^{\lfloor\frac{n}{x}\rfloor}\sum\limits_{j=1}^{{\lfloor\frac{m}{y}\rfloor}} \\
&=\sum\limits_{d=1}^{n}\mu(d)\sum\limits_{x=1}^{\lfloor \frac{n}{d} \rfloor}\sum\limits_{y=1}^{\lfloor \frac{m}{d} \rfloor}\lfloor\frac{n}{xd}\rfloor \lfloor\frac{m}{yd}\rfloor \\
&=\sum\limits_{d=1}^{n}\mu(d)\sum\limits_{x=1}^{\lfloor \frac{n}{d} \rfloor}\lfloor\frac{n}{xd}\rfloor\sum\limits_{y=1}^{\lfloor \frac{m}{d} \rfloor} \lfloor\frac{m}{yd}\rfloor \\
\end{aligned} i = 1 ∑ n j = 1 ∑ m d ( ij ) = i = 1 ∑ n j = 1 ∑ m x ∣ i ∑ y ∣ j ∑ [ g cd( x , y ) == 1 ] = x = 1 ∑ n y = 1 ∑ m [ g cd( x , y ) == 1 ] i = 1 ∑ ⌊ x n ⌋ j = 1 ∑ ⌊ y m ⌋ = d = 1 ∑ n μ ( d ) x = 1 ∑ ⌊ d n ⌋ y = 1 ∑ ⌊ d m ⌋ ⌊ x d n ⌋ ⌊ y d m ⌋ = d = 1 ∑ n μ ( d ) x = 1 ∑ ⌊ d n ⌋ ⌊ x d n ⌋ y = 1 ∑ ⌊ d m ⌋ ⌊ y d m ⌋ 定义f ( n ) = ∑ i = 1 n ⌊ n i ⌋ f(n)=\sum\limits_{i=1}^{n}\lfloor\frac{n}{i}\rfloor f ( n ) = i = 1 ∑ n ⌊ i n ⌋ O ( 1 ) O(1) O ( 1 )
原式 = ∑ d = 1 n μ ( d ) f ( ⌊ n d ⌋ ) f ( ⌊ m d ⌋ ) 原式=\sum\limits_{d=1}^{n}\mu(d)f(\lfloor \frac{n}{d} \rfloor) f(\lfloor \frac{m}{d} \rfloor) 原式 = d = 1 ∑ n μ ( d ) f (⌊ d n ⌋) f (⌊ d m ⌋)
代码实现
# define sandom signed # include <cstdio> # include <iostream> # define int long long using namespace std;
const int Z = 5e4 + 10 ;
inline int read ( ) { int x = 0 ; int f = 0 ; char c = getchar ( ) ; while ( ! isdigit ( c) ) f |= c == '-' , c = getchar ( ) ; while ( isdigit ( c) ) x = ( x << 1 ) + ( x << 3 ) + ( c ^ 48 ) , c = getchar ( ) ; return f ? - x : x; }
inline void write ( int x) { static int wrt[ 20 ] ; int TP = 0 ; if ( x < 0 ) putchar ( '-' ) , x = - x; while ( x >= 10 ) wrt[ ++ TP] = x % 10 , x /= 10 ; wrt[ ++ TP] = x; while ( TP) putchar ( wrt[ TP-- ] | 48 ) ; putchar ( '\n' ) ; }
int n, m, s, ans;
bool prime[ Z] ;
int ip[ Z] ;
int miu[ Z] , f[ Z] ;
void Mobius ( int n) {
miu[ 1 ] = 1 ;
for ( int i = 2 ; i <= n; i++ ) {
if ( ! prime[ i] ) ip[ ++ ip[ 0 ] ] = i, miu[ i] = - 1 ;
for ( int j = 1 ; j <= ip[ 0 ] ; j++ ) {
int k = i * ip[ j] ;
if ( k > n) break ;
prime[ k] = 1 ;
if ( i % ip[ j] == 0 ) { miu[ k] = 0 ; break ; }
else miu[ k] = - miu[ i] ;
}
}
for ( int i = 1 ; i <= n; i++ ) miu[ i] += miu[ i - 1 ] ;
}
void init ( int n) {
for ( int k = 1 ; k <= n; k++ )
for ( int l = 1 , r; l <= k; l = r + 1 ) {
r = k / ( k / l) ;
f[ k] += ( k / l) * ( r - l + 1 ) ;
}
}
inline int NTB ( int n, int m) {
int k = min ( n, m) ;
int ans = 0 ;
for ( int l = 1 , r; l <= k; l = r + 1 ) {
r = min ( n / ( n / l) , m / ( m / l) ) ;
ans += f[ n / l] * f[ m / l] * ( miu[ r] - miu[ l - 1 ] ) ;
}
return ans;
}
sandom main ( ) {
Mobius ( 5e4 ) ; init ( 5e4 ) ;
int T = read ( ) ;
while ( T-- ) {
n = read ( ) , m = read ( ) ;
write ( NTB ( n, m) ) ;
}
return 0 ;
}
∑ i = 1 n ∑ j = 1 m φ ( i j ) \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\varphi(ij) i = 1 ∑ n j = 1 ∑ m φ ( ij )
题目链接：毒瘤之神的考验
重要的性质：φ ( i j ) = φ ( i ) φ ( j ) gcd ( i , j ) φ ( gcd ( i , j ) ) \varphi(ij)=\frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))} φ ( ij ) = φ ( g c d ( i , j )) φ ( i ) φ ( j ) g c d ( i , j )
证明：从φ \varphi φ φ ( i j ) = i j ∏ p ∣ i o r p ∣ j ( 1 − 1 p ) ， φ ( gcd ( i , j ) ) = g c d ( i , j ) ∏ p ∣ i a n d p ∣ j ( 1 − 1 p ) ， φ ( i ) φ ( j ) = i j ∏ p ∣ i ( 1 − 1 p ) ∏ p ∣ j ( 1 − 1 p ) \varphi(ij)=ij\prod\limits_{p|i\ or\ p|j}(1-\frac{1}{p})， \varphi(\gcd(i, j))=gcd(i,j)\prod\limits_{p|i\ and\ p|j}(1-\frac{1}{p})，\varphi(i)\varphi(j)=ij\prod\limits_{p|i}(1-\frac{1}{p})\prod\limits_{p|j}(1-\frac{1}{p}) φ ( ij ) = ij p ∣ i or p ∣ j ∏ ( 1 − p 1 ) ， φ ( g cd( i , j )) = g c d ( i , j ) p ∣ i an d p ∣ j ∏ ( 1 − p 1 ) ， φ ( i ) φ ( j ) = ij p ∣ i ∏ ( 1 − p 1 ) p ∣ j ∏ ( 1 − p 1 )
∑ i = 1 n ∑ j = 1 m φ ( i j ) = ∑ i = 1 n ∑ j = 1 m φ ( i ) φ ( j ) gcd ( i , j ) φ ( gcd ( i , j ) ) = ∑ k = 1 n k φ ( k ) ∑ i = 1 n φ ( i ) ∑ j = 1 m φ ( j ) [ gcd ( i , j ) = = k ] = ∑ k = 1 n k φ ( k ) ∑ i = 1 ⌊ n k ⌋ φ ( i k ) ∑ j = 1 ⌊ m k ⌋ φ ( j k ) ∑ d ∣ gcd ( i , j ) μ ( d ) = ∑ k = 1 n k φ ( k ) ∑ d = 1 n μ ( d ) ∑ i = 1 ⌊ n k d ⌋ φ ( i k d ) ∑ j = 1 ⌊ m k d ⌋ φ ( j k d ) 令 t = k d ，原式 = ∑ t = 1 n ∑ k ∣ t k μ ( t k ) φ ( k ) ∑ i = 1 ⌊ n t ⌋ φ ( i t ) ∑ j = 1 ⌊ m t ⌋ φ ( j t ) \begin{aligned}
\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\varphi(ij)
&=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))} \\
&=\sum\limits_{k=1}^{n}\frac{k}{\varphi(k)}\sum\limits_{i=1}^{n}\varphi(i)\sum\limits_{j=1}^{m}\varphi(j)[\gcd(i,j)==k] \\
&=\sum\limits_{k=1}^{n}\frac{k}{\varphi(k)}\sum\limits_{i=1}^{\lfloor \frac{n}{k} \rfloor}\varphi(ik)\sum\limits_{j=1}^{\lfloor \frac{m}{k} \rfloor}\varphi(jk)\sum\limits_{d|\gcd(i,j)}\mu(d) \\
&=\sum\limits_{k=1}^{n}\frac{k}{\varphi(k)}\sum\limits_{d=1}^{n}\mu(d)\sum\limits_{i=1}^{\lfloor \frac{n}{kd} \rfloor}\varphi(ikd)\sum\limits_{j=1}^{\lfloor \frac{m}{kd} \rfloor}\varphi(jkd) \\
令t=kd，原式&=\sum\limits_{t=1}^{n}\sum\limits_{k|t}\frac{k\mu(\frac{t}{k})}{\varphi(k)}\sum\limits_{i=1}^{\lfloor \frac{n}{t} \rfloor}\varphi(it)\sum\limits_{j=1}^{\lfloor \frac{m}{t} \rfloor}\varphi(jt) \\
\end{aligned} i = 1 ∑ n j = 1 ∑ m φ ( ij ) 令 t = k d ，原式 = i = 1 ∑ n j = 1 ∑ m φ ( g cd( i , j )) φ ( i ) φ ( j ) g cd( i , j ) = k = 1 ∑ n φ ( k ) k i = 1 ∑ n φ ( i ) j = 1 ∑ m φ ( j ) [ g cd( i , j ) == k ] = k = 1 ∑ n φ ( k ) k i = 1 ∑ ⌊ k n ⌋ φ ( ik ) j = 1 ∑ ⌊ k m ⌋ φ ( j k ) d ∣ g c d ( i , j ) ∑ μ ( d ) = k = 1 ∑ n φ ( k ) k d = 1 ∑ n μ ( d ) i = 1 ∑ ⌊ k d n ⌋ φ ( ik d ) j = 1 ∑ ⌊ k d m ⌋ φ ( j k d ) = t = 1 ∑ n k ∣ t ∑ φ ( k ) k μ ( k t ) i = 1 ∑ ⌊ t n ⌋ φ ( i t ) j = 1 ∑ ⌊ t m ⌋ φ ( j t ) 定义f ( t ) = ∑ k ∣ t k μ ( t k ) φ ( k ) ， g ( t , n ) = ∑ i = 1 n φ ( i t ) f(t)=\sum\limits_{k|t}\frac{k\mu(\frac{t}{k})}{\varphi(k)}，g(t, n)=\sum\limits_{i=1}^{n}\varphi(it) f ( t ) = k ∣ t ∑ φ ( k ) k μ ( k t ) ， g ( t , n ) = i = 1 ∑ n φ ( i t )
原式 = ∑ t = 1 n f ( t ) g ( t , ⌊ n t ⌋ ) g ( t , ⌊ m t ⌋ ) 原式=\sum\limits_{t=1}^{n}f(t)g(t, \lfloor \frac{n}{t} \rfloor)g(t, \lfloor \frac{m}{t} \rfloor) 原式 = t = 1 ∑ n f ( t ) g ( t , ⌊ t n ⌋) g ( t , ⌊ t m ⌋) 但是发现还是不能在O ( n ) O(\sqrt{n}) O ( n ) h ( a , b , n ) = ∑ t = 1 n f ( t ) g ( t , a ) g ( t , b ) h(a, b, n)=\sum\limits_{t=1}^{n}f(t)g(t,a)g(t,b) h ( a , b , n ) = t = 1 ∑ n f ( t ) g ( t , a ) g ( t , b )
首先f f f g 、 h g、h g 、 h g ( t , n ) = g ( t , n − 1 ) + φ ( n t ) ， h ( a , b , n ) = h ( a , b , n − 1 ) + f ( n ) g ( n , a ) g ( n , b ) g(t,n)=g(t,n-1)+\varphi(nt)，h(a,b,n)=h(a,b,n-1)+f(n)g(n,a)g(n,b) g ( t , n ) = g ( t , n − 1 ) + φ ( n t ) ， h ( a , b , n ) = h ( a , b , n − 1 ) + f ( n ) g ( n , a ) g ( n , b )
h h h t t t ⌊ n t ⌋ \lfloor \frac{n}{t} \rfloor ⌊ t n ⌋ t t t ⌊ n t ⌋ \lfloor \frac{n}{t} \rfloor ⌊ t n ⌋ B B B [ 35 , 50 ] [35, 50] [ 35 , 50 ] h h h
当然需要用到一些卡常技巧，比如说动态内存池。
代码实现
# define sandom signed # include <bits/stdc++.h> using namespace std;
const int Z = 1e5 + 2 ; const int M = 50 ; const int mod = 998244353 ;
inline char getc ( ) { static char buf[ 1 << 18 ] , * p1, * p2; if ( p1 == p2) { p1 = buf, p2 = buf + fread ( buf, 1 , 1 << 18 , stdin ) ; if ( p1 == p2) return EOF ; } return * p1++ ; }
inline int read ( ) { int x = 0 , f = 0 ; char c = getc ( ) ; while ( ! isdigit ( c) ) f = c == '-' , c = getc ( ) ; while ( isdigit ( c) ) x = ( x << 1 ) + ( x << 3 ) + ( c ^ 48 ) , c = getc ( ) ; return f ? - x : x; }
inline void write ( int x) { static int wrt[ 20 ] ; int TP = 0 ; if ( x < 0 ) putchar ( '-' ) , x = - x; while ( x >= 10 ) wrt[ ++ TP] = x % 10 , x /= 10 ; wrt[ ++ TP] = x; while ( TP) putchar ( wrt[ TP-- ] | 48 ) ; putchar ( '\n' ) ; }
inline int max ( int a, int b) { return a > b ? a : b; } inline int min ( int a, int b) { return a < b ? a : b; }
inline int qpow ( int a, int b, int c) { int res = 1 ; while ( b) { if ( b & 1 ) res = 1ll * res * a % c; a = 1ll * a * a % c; b >>= 1 ; } return res; }
int n, m, ans;
bool prime[ Z] ;
int ip[ Z] , miu[ Z] , phi[ Z] , inv[ Z] ;
int f[ Z] , * g[ Z] , * h[ M + 2 ] [ M + 2 ] ;
void Linear ( int n) {
miu[ 1 ] = phi[ 1 ] = 1 ;
for ( int i = 2 ; i <= n; ++ i) {
if ( ! prime[ i] ) {
ip[ ++ ip[ 0 ] ] = i;
miu[ i] = - 1 ; phi[ i] = i - 1 ;
}
for ( int j = 1 ; j <= ip[ 0 ] ; ++ j) {
int k = i * ip[ j] ;
if ( k > n) break ;
prime[ k] = 1 ;
if ( i % ip[ j] == 0 ) { miu[ k] = 0 , phi[ k] = phi[ i] * ip[ j] ; break ; }
else miu[ k] = - miu[ i] , phi[ k] = phi[ i] * ( ip[ j] - 1 ) ;
}
}
for ( int i = 1 ; i <= n; ++ i) inv[ i] = qpow ( phi[ i] , mod - 2 , mod) ;
}
void init ( int n, int m) {
for ( int j = 1 ; j <= n; ++ j) for ( int i = j; i <= n; i += j) ( f[ i] += 1ll * j * miu[ i / j] * inv[ j] % mod) %= mod;
for ( int j = 1 ; j <= n; ++ j) {
int tmp = n / j;
g[ j] = new int [ tmp + 2 ] ( ) ;
for ( int i = 1 ; i <= tmp; ++ i) g[ j] [ i] = ( g[ j] [ i - 1 ] + phi[ i * j] ) % mod;
}
for ( int a = 1 ; a <= m; ++ a) for ( int b = 1 ; b <= m; ++ b) {
int tmp = n / max ( a, b) ;
h[ a] [ b] = new int [ tmp + 2 ] ( ) ;
for ( int i = 1 ; i <= tmp; ++ i) h[ a] [ b] [ i] = ( h[ a] [ b] [ i - 1 ] + 1ll * f[ i] * g[ i] [ a] % mod * g[ i] [ b] % mod) % mod;
}
}
int calc ( int a, int b, int l, int r) {
int res = 0 ;
for ( int i = l; i <= r; ++ i) ( res += 1ll * f[ i] * g[ i] [ a] % mod * g[ i] [ b] % mod) %= mod;
return res;
}
int solve ( int n, int m) {
ans = 0 ;
for ( int l = 1 , r; l <= n; l = r + 1 ) {
int tmp1 = n / l, tmp2 = m / l;
r = min ( n / tmp1, m / tmp2) ;
if ( max ( tmp1, tmp2) > M) ( ans += calc ( tmp1, tmp2, l, r) ) %= mod;
else ( ans += ( h[ tmp1] [ tmp2] [ r] - h[ tmp1] [ tmp2] [ l - 1 ] ) % mod) %= mod;
}
return ans;
}
sandom main ( ) {
int T = read ( ) ;
Linear ( 1e5 ) ; init ( 1e5 , M) ;
while ( T-- ) {
n = read ( ) , m = read ( ) ;
if ( n > m) swap ( n, m) ;
write ( ( solve ( n, m) + mod) % mod) ;
}
return 0 ;
}