[51Nod 1222]

Nod 1222]"/>

[51Nod 1222]

题面

求 ∑ k = a b ∑ i = 1 k ∑ j = 1 i [ l c m ( i , j ) = = k ] \large\sum_{k=a}^b\sum_{i=1}^k\sum_{j=1}^i[lcm(i,j)==k] k=a∑b​i=1∑k​j=1∑i​[lcm(i,j)==k]
1 &lt; = a &lt; = b &lt; = 1 0 11 1&lt;=a&lt;=b&lt;=10^{11} 1<=a<=b<=1011

题目分析

令 f ( n ) = ∑ i = 1 n ∑ j = 1 i [ l c m ( i , j ) = = n ] \large f(n)=\sum_{i=1}^n\sum_{j=1}^i[lcm(i,j)==n] f(n)=∑i=1n​∑j=1i​[lcm(i,j)==n]
则 A n s = ∑ i = a b f ( i ) \large Ans=\sum_{i=a}^bf(i) Ans=∑i=ab​f(i)
f ( n ) = ∑ i = 1 n ∑ j = 1 i [ i ⋅ j = = n ⋅ ( i , j ) ] = ∑ d ∣ n ∑ d ∣ i ∑ d ∣ j , j &lt; = i [ i ⋅ j = = n d &amp; &amp; ( i d , j d ) = = 1 ] = ∑ d ∣ n ∑ i = 1 n d ∑ j = 1 i [ i j = = n d &amp; &amp; ( i , j ) = = 1 ] = ∑ d ∣ n ∑ i = 1 d ∑ j = 1 i [ i j = = d &amp; &amp; ( i , j ) = = 1 ] = ∑ d ∣ n h ( d ) \large f(n)=\sum_{i=1}^n\sum_{j=1}^i[i\cdot j==n\cdot (i,j)]\\=\sum_{d|n}\sum_{d|i}\sum_{d|j,j&lt;=i}[i\cdot j==nd~\&amp;\&amp;~(\frac id,\frac jd)==1]\\=\sum_{d|n}\sum_{i=1}^{\frac nd}\sum_{j=1}^i[ij==\frac nd~\&amp;\&amp;~(i,j)==1]\\=\sum_{d|n}\sum_{i=1}^d\sum_{j=1}^i[ij==d~\&amp;\&amp;~(i,j)==1]\\=\sum_{d|n}h(d) f(n)=i=1∑n​j=1∑i​[i⋅j==n⋅(i,j)]=d∣n∑​d∣i∑​d∣j,j<=i∑​[i⋅j==nd && (di​,dj​)==1]=d∣n∑​i=1∑dn​​j=1∑i​[ij==dn​ && (i,j)==1]=d∣n∑​i=1∑d​j=1∑i​[ij==d && (i,j)==1]=d∣n∑​h(d)
此处 h ( d ) h(d) h(d)表示小于等于 d d d中,满足两个数互质且乘积为 d d d的无序数对的个数,显然
h ( d ) = { 1 , d = 1 2 ω ( d ) − 1 , d = ∏ i = 1 ω ( d ) p i a i \large h(d)=\left\{ \begin{aligned} &amp;1~,~d=1\\ &amp;2^{\omega(d)-1}~,~d=\prod_{i=1}^{\omega(d)}p_i^{a_i}\\ \end{aligned} \right. h(d)=⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧​​1 , d=12ω(d)−1 , d=i=1∏ω(d)​piai​​​其中 ω ( d ) \large\omega(d) ω(d)表示d的质因子个数

相当于把d的质因数分成两部分,所以就每个质因数选或不选,又因为是无序数对,所以除以2,也可以写为以下形式
h ( d ) = 2 ω ( d ) + [ d = = 1 ] 2 \large h(d)=\frac{2^{\omega(d)}+[d==1]}2 h(d)=22ω(d)+[d==1]​

• 有没有发现十分类似某个等式,记与 n n n互质的数的和为 a ( n ) a(n) a(n)(随便选的字母),则
• a ( n ) = φ ( n ) n + [ n = = 1 ] 2 a(n)=\frac{\varphi(n)n+[n==1]}2 a(n)=2φ(n)n+[n==1]​

回到这道题,有 f ( n ) = ∑ d ∣ n h ( d ) = ∑ d ∣ n 2 ω ( d ) + [ d = = 1 ] 2 = 1 + ∑ d ∣ n 2 ω ( d ) 2 \large f(n)=\sum_{d|n}h(d)=\sum_{d|n}\frac{2^{\omega(d)}+[d==1]}2\\=\frac{1+\sum_{d|n}2^{\omega(d)}}2 f(n)=d∣n∑​h(d)=d∣n∑​22ω(d)+[d==1]​=21+∑d∣n​2ω(d)​
然后我们又发现其实 2 ω ( d ) \large2^{\omega(d)} 2ω(d)是每个质因数选或不选的方案数,及 d d d的无平方因子的约数的个数,所以 2 ω ( d ) = ∑ k ∣ d ∣ μ ( k ) ∣ \large 2^{\omega(d)}=\sum_{k|d}|\mu(k)| 2ω(d)=k∣d∑​∣μ(k)∣根据 μ \mu μ函数的定义,我们知道只有无平方因子数的函数值才为1或-1,所以加上绝对值就成了计数
∴ ∑ i = 1 n f ( i ) = n + ∑ i = 1 n ∑ d ∣ i 2 ω ( d ) 2 = n + ∑ i = 1 n ∑ d ∣ i ∑ k ∣ d ∣ μ ( k ) ∣ 2 \large \therefore \sum_{i=1}^nf(i)=\frac{n+\sum_{i=1}^n\sum_{d|i}2^{\omega(d)}}2=\frac{n+\sum_{i=1}^n\sum_{d|i}\sum_{k|d}|\mu(k)|}2 ∴i=1∑n​f(i)=2n+∑i=1n​∑d∣i​2ω(d)​=2n+∑i=1n​∑d∣i​∑k∣d​∣μ(k)∣​
∵ ∑ i = 1 n ∑ d ∣ i ∑ k ∣ d ∣ μ ( k ) ∣ = ∑ k = 1 n ∣ μ ( k ) ∣ ∑ k ∣ d ∑ d ∣ i 1 = ∑ k = 1 n ∣ μ ( k ) ∣ ∑ k ∣ d ⌊ n d ⌋ = ∑ k = 1 n ∣ μ ( k ) ∣ ∑ d = 1 ⌊ n k ⌋ ⌊ n d k ⌋ = ∑ k = 1 n ∣ μ ( k ) ∣ ∑ d = 1 ⌊ n k ⌋ ⌊ ⌊ n k ⌋ d ⌋ = ∑ k = 1 n ∣ μ ( k ) ∣ ∑ d = 1 ⌊ n k ⌋ ⌊ ⌊ n k ⌋ d ⌋ \large\because \sum_{i=1}^n\sum_{d|i}\sum_{k|d}|\mu(k)|=\sum_{k=1}^n|\mu(k)|\sum_{k|d}\sum_{d|i}1\\=\sum_{k=1}^n|\mu(k)|\sum_{k|d}\lfloor\frac nd\rfloor\\=\sum_{k=1}^n|\mu(k)|\sum_{d=1}^{\lfloor\frac nk\rfloor}\lfloor\frac n{dk}\rfloor\\=\sum_{k=1}^n|\mu(k)|\sum_{d=1}^{\lfloor\frac nk\rfloor}\lfloor\frac {\lfloor\frac nk\rfloor}d\rfloor\\=\sum_{k=1}^n|\mu(k)|\sum_{d=1}^{\lfloor\frac nk\rfloor}\lfloor\frac {\lfloor\frac nk\rfloor}d\rfloor ∵i=1∑n​d∣i∑​k∣d∑​∣μ(k)∣=k=1∑n​∣μ(k)∣k∣d∑​d∣i∑​1=k=1∑n​∣μ(k)∣k∣d∑​⌊dn​⌋=k=1∑n​∣μ(k)∣d=1∑⌊kn​⌋​⌊dkn​⌋=k=1∑n​∣μ(k)∣d=1∑⌊kn​⌋​⌊d⌊kn​⌋​⌋=k=1∑n​∣μ(k)∣d=1∑⌊kn​⌋​⌊d⌊kn​⌋​⌋

• 先看第二个 ∑ \large\sum ∑，对于某一个 ⌊ n k ⌋ \large{\lfloor\frac nk\rfloor} ⌊kn​⌋的取值，把它记作 N N N，就以 N N N的范围做整除分块优化， Θ ( N ) \large\Theta(\sqrt N) Θ(N ​)的时间复杂度，那么外层还有一个求和，于是在外面也套一层整除分块优化，预处理出前 n 2 3 \large n^{\frac 23} n32​后时间复杂度为 Θ ( n 2 3 ) \large\Theta(n^{\frac23}) Θ(n32​)

  • 此处预处理为线性筛，考虑变换， ∑ i = 1 n ⌊ n i ⌋ \large\sum_{i=1}^n\large{\lfloor\frac ni\rfloor} ∑i=1n​⌊in​⌋实际可看作枚举 i i i后看 n n n以内有多少个数能被 i i i整除，这不就是 ∑ i = 1 n σ 0 ( i ) \large\sum_{i=1}^n\sigma_0(i) ∑i=1n​σ0​(i)吗？(这个函数表示i的约数个数)
    于是我们只需要筛出约数个数在累加就行了，线性筛时存一下当前数的最小质因子的次数就可以愉快的线性筛了

• 由于在外面一层套上了整除分块优化，则需要求出 ∣ μ ( k ) ∣ \large |\mu(k)| ∣μ(k)∣的前缀和，也就是 n n n以内的无平方因子数

  • 这里处理无平方因子数时用容斥原理，有
    ∑ i = 1 n ∣ μ ( i ) ∣ = ∑ i = 1 n μ ( i ) ⋅ ⌊ n i 2 ⌋ \large\sum_{i=1}^n|\mu(i)|=\sum_{i=1}^{\sqrt n}\mu(i)\cdot\lfloor\frac n{i^2}\rfloor i=1∑n​∣μ(i)∣=i=1∑n ​​μ(i)⋅⌊i2n​⌋想想 μ \mu μ函数的定义，这个容斥还是比较好理解的
    Θ ( n ) \large \Theta(\sqrt n) Θ(n ​)可处理出来

• 其实这道题用的是[SPOJ] DIVCNT2 - Counting Divisors (square)一模一样的方法(我后面的分析都是直接粘的233)

• 但是奈何这道题 T M \color{white}TM TM的卡内存!(各种预处理+卡内存我只能做到6015ms>6000ms T了…)

• 只能想想别的办法(也许有些同学掌握特殊的卡常技巧能过A掉吧)

.
.
.
.
.
好的。

正文开始

那么我就要开始略讲一点了

定义 F ( i ) = ∑ x = 1 i ∑ y = 1 x [ x y ( x , y ) = = i ] \large F(i)=\sum_{x=1}^i\sum_{y=1}^x[\frac{xy}{(x,y)}==i] F(i)=∑x=1i​∑y=1x​[(x,y)xy​==i]
则 A n s = ∑ i = 1 b F ( i ) − ∑ i = 1 a − 1 F ( i ) \large Ans=\sum_{i=1}^bF(i)-\sum_{i=1}^{a-1}F(i) Ans=∑i=1b​F(i)−∑i=1a−1​F(i)

考虑 ∑ i = 1 n F ( i ) \sum_{i=1}^nF(i) ∑i=1n​F(i)怎么求
设 ( x , y ) = r , x = a r , y = b r (x,y)=r,x=ar,y=br (x,y)=r,x=ar,y=br,则
∑ i = 1 n F ( i ) = ∑ x = 1 n ∑ y = 1 x [ x y r ≤ n ] = ∑ a ∑ b ∑ r [ a ≤ b ] [ ( a , b ) = = 1 ] [ a b r ≤ n ] \large \sum_{i=1}^nF(i)=\sum_{x=1}^n\sum_{y=1}^x[\frac {xy}r\le n]\\=\sum_a\sum_b\sum_r[a\le b][(a,b)==1][abr\le n] i=1∑n​F(i)=x=1∑n​y=1∑x​[rxy​≤n]=a∑​b∑​r∑​[a≤b][(a,b)==1][abr≤n]反演一下得到 ∑ i = 1 n F ( i ) = ∑ d = 1 n μ ( d ) ∑ a ∑ b ∑ r [ a ≤ b ] [ a b r ≤ ⌊ n d 2 ⌋ ] \large \sum_{i=1}^nF(i)=\sum_{d=1}^{\sqrt n}\mu(d)\sum_a\sum_b\sum_r[a\le b][abr\le \lfloor\frac n{d^2}\rfloor] i=1∑n​F(i)=d=1∑n ​​μ(d)a∑​b∑​r∑​[a≤b][abr≤⌊d2n​⌋]不考虑 [ a ≤ b ] [a\le b] [a≤b]的话就是 a , b , r a,b,r a,b,r三个数的乘积的统计,做法为统计 x ≤ y ≤ z &amp; &amp; x y z ≤ N x\le y\le z~\&amp;\&amp;~xyz\le N x≤y≤z && xyz≤N的 ( x , y , z ) (x,y,z) (x,y,z)数对的数量

分别考虑三个数不相等/两个数相等/三个数相等的情况再分别乘上排列系数

由于这样的枚举只需要枚举 x ≤ N 1 3 \large x\le N^{\frac 13} x≤N31​,在枚举 x ≤ y ≤ N x \large x\le y\le \frac Nx x≤y≤xN​,然后 Θ ( 1 ) \Theta(1) Θ(1)统计 z z z的个数

[ a ≤ b ] [a\le b] [a≤b]比较讨厌,假设 ( a , b ) (a,b) (a,b)与 ( b , a ) (b,a) (b,a)被统计两次,因为有 a = b a=b a=b的情况不能直接除以 2 2 2
回到原问题,当 a = b a=b a=b时,由于 ( a , b ) = 1 (a,b)=1 (a,b)=1,所以 a = b = 1 a=b=1 a=b=1,此时 r r r有 n n n种取值,所以只需要在算出的结果加上 n n n再除以 2 2 2即可
参考自 51Nod 题解1楼

时间复杂度证明

设 T ( n ) T(n) T(n)表示统计满足 x y z &lt; = n xyz&lt;=n xyz<=n的 ( x , y , z ) (x,y,z) (x,y,z)的三元组个数的时间复杂度
T ( n ) = Θ ( ∑ x = 1 n 1 3 ( n x − x ) ) = Θ ( n 2 3 ) \large T(n)=\Theta\left(\sum_{x=1}^{n^{\frac 13}}(\sqrt{\frac nx}-x)\right)=\Theta(n^{\frac 23}) T(n)=Θ⎝⎜⎜⎛​x=1∑n31​​(xn​ ​−x)⎠⎟⎟⎞​=Θ(n32​)
上面的 − x -x −x是枚举 y y y时从 x + 1 x+1 x+1开始枚举,总时间复杂度 = Θ ( ∑ d = 1 n T ( n d 2 ) ) = Θ ( ∑ d = 1 n T ( ( n d ) 2 ) ) = Θ ( ∑ d = 1 n ( n d ) 4 3 ) = Θ ( ∑ d = 1 n ( n 2 3 d 4 3 ) ) = Θ ( n 2 3 ∑ d = 1 n ( 1 d 4 3 ) ) \large =\Theta\left(\sum_{d=1}^{\sqrt n}T(\frac n{d^2})\right)\\=\Theta\left(\sum_{d=1}^{\sqrt n}T((\frac{\sqrt n}d)^2)\right)\\=\Theta\left(\sum_{d=1}^{\sqrt n}(\frac{\sqrt n}d)^{\frac 43}\right)\\=\Theta\left(\sum_{d=1}^{\sqrt n}(\frac{n^{\frac 23}}{d^{\frac 43}})\right)\\=\Theta\left(n^{\frac 23}\sum_{d=1}^{\sqrt n}(\frac{1}{d^{\frac 43}})\right) =Θ⎝⎜⎛​d=1∑n ​​T(d2n​)⎠⎟⎞​=Θ⎝⎜⎛​d=1∑n ​​T((dn ​​)2)⎠⎟⎞​=Θ⎝⎜⎛​d=1∑n ​​(dn ​​)34​⎠⎟⎞​=Θ⎝⎜⎛​d=1∑n ​​(d34​n32​​)⎠⎟⎞​=Θ⎝⎜⎛​n32​d=1∑n ​​(d34​1​)⎠⎟⎞​此处 d d d的枚举应该是离散的,我们将它看做连续的,由于 n = n 1 2 \sqrt n=n^{\frac 12} n ​=n21​那么将 d d d两两结合,有
∫ 1 n 1 4 ( 1 x 4 3 ) + ( 1 ( n 1 2 x 3 4 ) ) d x &gt; = ∫ 1 n 1 4 2 ( 1 x 4 3 ( n 1 2 x 3 4 ) ) d x = ∫ 1 n 1 4 2 ( 1 n 1 2 ) d x \large\int_{1}^{n^{\frac 14}} (\frac 1{x^{\frac 43}})+(\frac 1{(\frac{n^{\frac 12}}{x^{\frac 34}})})dx\\&gt;=\int_{1}^{n^{\frac 14}} 2\left(\frac 1{x^{\frac 43}{(\frac{n^{\frac 12}}{x^{\frac 34}})}}\right)dx\\=\int_{1}^{n^{\frac 14}} 2\left(\frac 1{n^{\frac 12}}\right)dx ∫1n41​​(x34​1​)+((x43​n21​​)1​)dx>=∫1n41​​2⎝⎜⎜⎛​x34​(x43​n21​​)1​⎠⎟⎟⎞​dx=∫1n41​​2(n21​1​)dx于是我们又回到离散的,最多有 n 1 2 2 \frac{n^\frac 12}2 2n21​​对这样的关系,所以
∑ d = 1 n ( 1 d 4 3 ) = n 1 2 2 ⋅ 2 ( 1 n 1 2 ) = 1 \large \sum_{d=1}^{\sqrt n}(\frac{1}{d^{\frac 43}})=\frac{n^\frac 12}2\cdot2\left(\frac 1{n^{\frac 12}}\right)=1 d=1∑n ​​(d34​1​)=2n21​​⋅2(n21​1​)=1所以总时间复杂度为 Θ ( n 2 3 ∑ d = 1 n ( 1 d 4 3 ) ) = Θ ( n 2 3 ) \large \Theta\left(n^{\frac 23}\sum_{d=1}^{\sqrt n}(\frac{1}{d^{\frac 43}})\right)=\Theta(n^{\frac 23}) Θ⎝⎜⎛​n32​d=1∑n ​​(d34​1​)⎠⎟⎞​=Θ(n32​)
申明:以上的 ∫ \int ∫符号纯属乱用,只是不能再用 ∑ \sum ∑表示 x x x的取值可能不为整数的和了

AC code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 316228;
int Cnt, Prime[N], mu[N];
bool IsnotPrime[N];void init()
{mu[1] = 1;for(int i = 2; i < N; ++i){if(!IsnotPrime[i])Prime[++Cnt] = i, mu[i] = -1;for(int j = 1; j <= Cnt && i * Prime[j] < N; ++j){IsnotPrime[i * Prime[j]] = 1;if(i % Prime[j] == 0) { mu[i * Prime[j]] = 0; break; }mu[i * Prime[j]] = -mu[i];}}
}LL solve(LL n)
{LL ret = n;for(int d = 1; (LL)d*d <= n; ++d) if(mu[d]){LL m = n/((LL)d*d), s = 0;for(int a = 1; (LL)a*a*a <= m; ++a){for(int b = a+1; (LL)a*b*b <= m; ++b)s += (m/((LL)a*b)-b) * 6 + 3; // * 6 -> a < b < c ( P(3,3) = 6 )// + 3 -> a < b = c ( P(3,3)/P(2,2) = 3)s += (m/((LL)a*a)-a) * 3 + 1; // * 3 -> a = b < c ( P(3,3)/P(2,2) = 3 )// + 1 -> a = b = c}//以上的"-b","-a"都是为了满足 c>b 或 c>b=a,跟时间复杂度的分析一样ret += s * mu[d];}return ret / 2;
}int main ()
{LL a, b; init();scanf("%lld%lld", &a, &b);printf("%lld\n", solve(b)-solve(a-1));
}

.
.
可写死我了