莫比乌斯反演总结

编程入门行业动态更新时间:2024-10-20 05:46:44

莫比<a href=https://www.elefans.com/category/jswz/34/1757709.html style= 乌斯反演总结"/>

莫比乌斯反演总结

此总结写于18年10月左右, 忘记放在CSDN上共享了, 现在补一下.
同时提供markdown的源文件供下载修改成自己的模板, 也可在其中查看博客里面渲染失败的公式
链接: 提取码: 8t4c

莫比乌斯反演

约定

1.任何一个数可以被表示成: P = p 1 q 1 ⋅ p 2 q 2 ⋅ p 3 q 3 ⋯ p t q t P=p_1^{q_{1}}\cdot{p_2^{q_{2}}}\cdot{p_3^{q_{3}}}\cdots{p_t^{q_{t}}} P=p1q1⋅p2q2⋅p3q3⋯ptqt

并约定: q 1 + q 2 + q 3 + . . . + q t = t s u m q_1+q_2+q_3+...+q_t=tsum q1+q2+q3+...+qt=tsum.

2. d ( x ) d(x) d(x)表示 x x x的约数个数,即约数个数函数.

3. σ ( x ) \sigma(x) σ(x)表示 x x x的约数和,即约数和函数.

4. w ( x ) w(x) w(x)表示 x x x的不同质因子个数.

5.未特别注明且 n n n 不一定能整除 k k k 的 n k \frac{n}{k} kn 均表示 ⌊ n k ⌋ \lfloor {\frac{n}{k}} \rfloor ⌊kn⌋ .

6.未注明范围的题均是 1 0 5 10^5 105 ~ 1 0 12 10^{12} 1012 都可以做的题.

7.题目中未特别注明的题,都根据范围考虑取模或不取模.

基本概念

莫比乌斯函数

莫比乌斯函数是一个由容斥系数所构成的函数. μ ( n ) \mu(n) μ(n) 的定义如下:

当 n = 1 n=1 n=1 时, μ ( n ) = 1 \mu(n)=1 μ(n)=1
当 n = ∏ i = 1 t p i n=\prod_{i=1}^tp_i n=∏i=1tpi 且 p i p_i pi 为不同的素数时, μ ( n ) = ( − 1 ) t \mu(n)=(-1)^t μ(n)=(−1)t . 即 n n n 分解质因子后没有幂次大于等于平方的质因子,此时函数值根据分解的个数决定.
当 n n n 含有任何质因子的幂次大于等于 2 2 2 时, μ ( n ) = 0 \mu(n)=0 μ(n)=0

莫比乌斯反演

定理 : F ( n ) F(n) F(n) 和 f ( n ) f(n) f(n) 是定义在非负整数集合上的两个函数,并且满足条件 :

F ( n ) = ∑ d ∣ n f ( d ) F(n)=\sum_{d|n}f(d) F(n)=d∣n∑f(d)

那么存在一个结论 :

f ( n ) = ∑ d ∣ n μ ( d ) ⋅ F ( n d ) f(n)=\sum_{d|n}\mu(d)\cdot{F(\frac{n}{d})} f(n)=d∣n∑μ(d)⋅F(dn)
更常用的形式: 如果 F ( n ) F(n) F(n) 和 f ( n ) f(n) f(n) 满足条件:

F ( n ) = ∑ n ∣ d f ( d ) F(n)=\sum_{n|d}f(d) F(n)=∑n∣df(d)

那么存在一个结论:

f ( n ) = ∑ n ∣ d μ ( d n ) ⋅ F ( d ) f(n)=\sum_{n|d}\mu(\frac{d}{n})\cdot{F(d)} f(n)=∑n∣dμ(nd)⋅F(d)

杜教筛

作用: 以低于线性的时间复杂度来计算积性函数的前缀和(常为 O ( n 2 3 ) O(n^{\frac{2}{3}}) O(n32)).

前提 : 对于一个积性函数 f ( i ) f(i) f(i) ,如果知道 ∑ d ∣ n f ( d ) = g ( n ) \sum_{d|n}f(d) = g(n) ∑d∣nf(d)=g(n) ,且 g ( n ) g(n) g(n) 非常容易求出来,那么就可以用杜教筛快速求出 ∑ i = 1 n f ( i ) \sum_{i=1}^nf(i) ∑i=1nf(i) .

预处理 : 通常预处理出 ∑ i = 1 n f ( i ) \sum_{i=1}^nf(i) ∑i=1nf(i) 的前 n 2 3 n^{\frac{2}{3}} n32 项 .

原理 : 假设现在要求 ∑ i = 1 n φ ( i ) \sum_{i=1}^n \varphi(i) ∑i=1nφ(i) , 我们知道 ∑ d ∣ n φ ( d ) = n \sum_{d|n}\varphi(d) = n ∑d∣nφ(d)=n .

将 ∑ d ∣ n φ ( d ) = n \sum_{d|n}\varphi(d) = n ∑d∣nφ(d)=n 拆分移项可以得到 : φ ( n ) = n − ∑ d ∣ n , d < n φ ( d ) \varphi(n) = n - \sum_{d|n,d\lt{n}}\varphi(d) φ(n)=n−∑d∣n,d<nφ(d)

将式子左右两端同时取和得 : ∑ i = 1 n φ ( i ) = ∑ i = 1 n i − ∑ i = 1 n ∑ d ∣ i , d < i φ ( d ) \sum_{i=1}^n\varphi(i) = {\sum_{i=1}^n i} - \sum_{i=1}^n\sum_{d|i,d\lt{i}}\varphi(d) ∑i=1nφ(i)=∑i=1ni−∑i=1n∑d∣i,d<iφ(d) .

考虑将右边的式子更换枚举项由 i i i 变成 i d \frac{i}{d} di 得: ∑ i = 1 n φ ( i ) = ∑ i = 1 n i − ∑ i = 2 n ∑ d = 1 n i φ ( d ) \sum_{i=1}^n\varphi(i) = {\sum_{i=1}^ni} - \sum_{i=2}^n\sum_{d=1}^{\frac{n}{i}}\varphi(d) ∑i=1nφ(i)=∑i=1ni−∑i=2n∑d=1inφ(d)

此时容易发现可以可以分块+记忆化处理.

常用式子总结:

∑ i = 1 n μ ( i ) = 1 − ∑ i = 2 n ∑ d = 1 n i μ ( d ) \sum_{i=1}^n\mu(i) = 1 - \sum_{i=2}^n\sum_{d=1}^{\frac{n}{i}}\mu(d) ∑i=1nμ(i)=1−∑i=2n∑d=1inμ(d)

∑ i = 1 n i ⋅ μ ( i ) = 1 − ∑ i = 2 n i ⋅ ∑ d = 1 n i d ⋅ μ ( d ) \sum_{i=1}^ni\cdot\mu(i) = 1 - \sum_{i=2}^ni\cdot\sum_{d=1}^{\frac{n}{i}}d\cdot\mu(d) ∑i=1ni⋅μ(i)=1−∑i=2ni⋅∑d=1ind⋅μ(d)

∑ i = 1 n φ ( i ) = ∑ i = 1 n i − ∑ i = 2 n ∑ d = 1 n i φ ( d ) \sum_{i=1}^n\varphi(i) = {\sum_{i=1}^ni} - \sum_{i=2}^n\sum_{d=1}^{\frac{n}{i}}\varphi(d) ∑i=1nφ(i)=∑i=1ni−∑i=2n∑d=1inφ(d)

∑ i = 1 n i ⋅ φ ( i ) = ∑ i = 1 n i 2 − ∑ i = 2 n i ⋅ ∑ d = 1 n i d ⋅ φ ( d ) \sum_{i=1}^ni\cdot\varphi(i) = {\sum_{i=1}^ni^2} - \sum_{i=2}^ni\cdot\sum_{d=1}^{\frac{n}{i}}d\cdot\varphi(d) ∑i=1ni⋅φ(i)=∑i=1ni2−∑i=2ni⋅∑d=1ind⋅φ(d)

∑ i = 1 n i 2 ⋅ φ ( i ) = ∑ i = 1 n i 3 − ∑ i = 2 n i 2 ⋅ ∑ d = 1 n i d 2 ⋅ φ ( d ) \sum_{i=1}^ni^2\cdot\varphi(i) = {\sum_{i=1}^ni^3} - \sum_{i=2}^ni^2\cdot\sum_{d=1}^{\frac{n}{i}}d^2\cdot\varphi(d) ∑i=1ni2⋅φ(i)=∑i=1ni3−∑i=2ni2⋅∑d=1ind2⋅φ(d)

常用性质

1.设 g ( n ) = ∑ i = 1 n ⌈ n i ⌉ g(n)=\sum_{i=1}^n\lceil{\frac{n}{i}}\rceil g(n)=∑i=1n⌈in⌉ , 那么 g ( n ) = g ( n − 1 ) + d ( n − 1 ) + 1 g(n)=g(n-1)+d(n-1)+1 g(n)=g(n−1)+d(n−1)+1 , d ( i ) d(i) d(i)为约数个数函数.

2. d ( i ⋅ j ) = ∑ x ∣ i ∑ y ∣ j [ gcd ⁡ ( x , y ) = = 1 ] d(i\cdot{j}) = \sum_{x|i}\sum_{y|j}[\gcd(x,y)==1] d(i⋅j)=∑x∣i∑y∣j[gcd(x,y)==1].

3. σ ( i ⋅ j ) = ∑ x ∣ i ∑ y ∣ j ( x ⋅ j y ) [ gcd ⁡ ( x , y ) = = 1 ] \sigma(i\cdot{j})=\sum_{x|i}\sum_{y|j} (x\cdot\frac{j}{y}) [\gcd(x,y)==1] σ(i⋅j)=∑x∣i∑y∣j(x⋅yj)[gcd(x,y)==1] .

4.设 f ( n ) f(n) f(n) 为 1 1 1 ~ n n n 中无平方因子的数的数量.则 f ( n ) = ∑ i = 1 n μ ( i 2 ) = ∑ i = 1 n μ ( i ) ⋅ n i 2 f(n) =\sum_{i=1}^n\mu(i^2)= \sum_{i=1}^{\sqrt{n}} \mu(i)\cdot\frac{n}{i^2} f(n)=∑i=1nμ(i2)=∑i=1n μ(i)⋅i2n

5. ∑ i = 1 n i ⋅ ⌊ n i ⌋ = ∑ i = 1 n ∑ j = 1 n i j = ∑ i = 1 n σ ( i ) \sum_{i=1}^ni\cdot{\lfloor\frac{n}{i}\rfloor}=\sum_{i=1}^n\sum_{j=1}^{\frac{n}{i}}j=\sum_{i=1}^n\sigma(i) ∑i=1ni⋅⌊in⌋=∑i=1n∑j=1inj=∑i=1nσ(i) .

6. ∑ d ∣ n μ ( d ) = [ n = = 1 ] \sum_{d|n}\mu(d)=[n==1] ∑d∣nμ(d)=[n==1]

7. ∑ d ∣ n μ ( d ) d = φ ( n ) n \sum_{d|n}\frac{\mu(d)}{d}=\frac{\varphi(n)}{n} ∑d∣ndμ(d)=nφ(n)

8. ∑ d ∣ n φ ( d ) = n \sum_{d|n}\varphi(d)=n ∑d∣nφ(d)=n

9. ∑ i = 1 n i ⋅ [ gcd ⁡ ( i , n ) = = 1 ] = n ⋅ φ ( n ) + [ n = = 1 ] 2 \sum_{i=1}^ni\cdot[\gcd(i,n)==1] =\frac{n\cdot\varphi(n)+[n==1]}{2} ∑i=1ni⋅[gcd(i,n)==1]=2n⋅φ(n)+[n==1]

10. 2 w ( n ) = ∑ d ∣ n μ 2 ( d ) 2^{w(n)}=\sum_{d|n}\mu^2(d) 2w(n)=∑d∣nμ2(d)

11. φ ( i k ) = i k − 1 ⋅ φ ( i ) \varphi(i^k)=i^{k-1}\cdot\varphi(i) φ(ik)=ik−1⋅φ(i)

12. ∑ i = 1 n ∑ j = 1 n [ gcd ⁡ ( i , j ) = = 1 ] = 2 ⋅ ∑ i = 1 n φ ( i ) − 1 \sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)==1]=2\cdot\sum_{i=1}^n\varphi(i)-1 ∑i=1n∑j=1n[gcd(i,j)==1]=2⋅∑i=1nφ(i)−1

小技巧

1.对于要求 ∑ i = 1 n f [ i ] x \sum_{i=1}^n\frac{f[i]}{x} ∑i=1nxf[i] , ∏ i = 1 n f [ i ] x \prod_{i=1}^n\frac{f[i]}{x} ∏i=1nxf[i]的情况(f为给定的数组,x为给定的值),如果 f [ i ] f[i] f[i]的范围较小, 可以把 f f f数组里面的值装入桶里,然后做一次前缀和,再根据x值来分块计算.从而将式子转化成: ∑ i = 1 m a x i ⋅ ( s u m [ x ⋅ i + x − 1 ] − s u m [ x ⋅ i − 1 ] ) \sum_{i=1}^{max}i\cdot(sum[x\cdot{i}+x-1]-sum[x\cdot{i}-1]) ∑i=1maxi⋅(sum[x⋅i+x−1]−sum[x⋅i−1]) , ∏ i = 1 m a x i ( s u m [ x ⋅ i + x − 1 ] − s u m [ x ⋅ i − 1 ] ) \prod_{i=1}^{max}i^{(sum[x\cdot{i}+x-1]-sum[x\cdot{i}-1])} ∏i=1maxi(sum[x⋅i+x−1]−sum[x⋅i−1]) .

2.对于一个数组 a 1 , a 2 , a 3 ⋯ a n a_1,a_2,a_3\cdots{a_n} a1,a2,a3⋯an 求每一个元素的逆元, 可以先做一次前缀积得到数组 S S S.然后我们可以快速求出 S n S_n Sn ~ S 1 S_1 S1 的逆元,那么 a n a_n an 的逆元就等于 S n S_n Sn 的逆元乘以 S n − 1 S_{n-1} Sn−1 .

下面以斐波那契数列为例求逆元:

void init()
{fib[0]=0;fib[1]=1;multi_fib[0]=multi_fib[1]=1;invfib[0]=invfib[1]=1;for(int i=2;i<=maxn;i++){fib[i]=(fib[i-1]+fib[i-2])%mod;multi_fib[i]=multi_fib[i-1]*fib[i]%mod;//预处理fib的前缀积}invfib[maxn]=qpow(multi_fib[maxn],mod-2);for(int i=maxn;i>=2;i--){invfib[i-1]=invfib[i]*fib[i]%mod;//先给invfib[i-1]赋值为前i-1项前缀积的逆元invfib[i]=invfib[i]*multi_fib[i-1]%mod;//更新invfib为fib[i]的逆元.}
}

3.有些函数本身就可以分块的处理出来的,在范围比较大的时候,可以用杜教筛的思想预处理出前 n 2 3 n^{\frac{2}{3}} n32 项,然后分块的处理后 n 1 3 n^{\frac{1}{3}} n31 项.

线性筛各种积性函数

关键: 线性筛积性函数 f ( n ) f(n) f(n),只需要知道 f ( p ) f(p) f(p) 的值和 f ( p k ) f(p^k) f(pk) 即可做到线性筛.

1.莫比乌斯函数 μ ( i ) \mu(i) μ(i):

f ( p ) = − 1 f(p)=-1 f(p)=−1 , f ( p k ) = 0 ( k > 1 ) f(p^k)=0(k>1) f(pk)=0(k>1).

void make()
{mu[1]=1;for(int i=2;i<=maxn;i++){if(!prime[i]) prime[++prime[0]]=i,mu[i]=-1;for(int j=1;j<=prime[0]&&prime[j]<=maxn/i;j++){prime[i*prime[j]]=1;if(i%prime[j]==0) break;else mu[i*prime[j]]=-mu[i];}}
}

2.欧拉函数 φ ( i ) \varphi(i) φ(i) :

f ( p ) = p − 1 , f ( p k ) = f ( p k − 1 ) ⋅ p f(p) = p-1 , f(p^k) = f(p^{k-1}) \cdot {p} f(p)=p−1,f(pk)=f(pk−1)⋅p

void make()
{phi[1]=1;for(int i=2;i<=maxn;i++){if(!prime[i]) prime[++prime[0]]=i,phi[i]=i-1;for(int j=1;j<=prime[0]&&prime[j]<=maxn/i;j++){prime[i*prime[j]]=1;if(i%prime[j]==0) { phi[i*prime[j]]=phi[i]*prime[j]; break;}else phi[i*prime[j]]=phi[i]*phi[prime[j]];}}
}

3.约数个数函数 d ( i ) : d(i): d(i):

f ( p ) = 2 , f ( p k ) = k + 1 f(p)=2,f(p^k)=k+1 f(p)=2,f(pk)=k+1

void make()
{d[1]=1;for(int i=2;i<=maxn;i++){if(!prime[i]){prime[++prime[0]]=i;d[i]=2; pow_cnt[i]=1;//pow_cnt记录最小质因子的幂次.}for(int j=1;j<=prime[0]&&prime[j]<=maxn/i;j++){int to=i*prime[j]; prime[to]=1;if(i%prime[j]==0){pow_cnt[to]=pow_cnt[i]+1;d[to]=d[i]/(pow_cnt[i]+1)*(pow_cnt[to]+1);break;}else{pow_cnt[to]=1; d[to]=d[i]*d[prime[j]];}}}
}

4.约数和函数 σ ( i ) : \sigma(i): σ(i):

f ( p ) = p + 1 , f ( p k ) = p 0 + p 1 + ⋯ + p k f(p)=p+1,f(p^k)=p^0+p^1+\cdots+p^k f(p)=p+1,f(pk)=p0+p1+⋯+pk

void make()
{d_sum[1]=1;//表示约数和函数for(int i=2;i<=maxn;i++){if(!prime[i]){prime[++prime[0]]=i;  d_sum[i]=i+1;//素数的话约数和就是i+1.prime_pow_count[i]=i+1;//素数对应的最小质因子幂和就是i+1.}for(int j=1;j<=prime[0]&&prime[j]<=maxn/i;j++){int to=i*prime[j]; prime[to]=1;if(i%prime[j]==0){//如果不是互素的话,说明当前的i中至少含有一个prime[j].prime_pow_count[to]=prime_pow_count[i]*prime[j]+1;//先除去之前的,再重新乘上去即可.d_sum[to]=d_sum[i]/prime_pow_count[i]*prime_pow_count[to];break; }else {prime_pow_count[to]=prime[j]+1;d_sum[to]=d_sum[i]*d_sum[prime[j]];//由于约数和函数是积性函数,所以互质的情况下等于直接相乘.}}}
}

5. σ ( i 2 ) \sigma(i^2) σ(i2) :

f ( p ) = p 2 + p + 1 , f ( p k ) = p 0 + p 1 + p 2 + ⋯ + p k + ⋯ + p 2 ⋅ k f(p)=p^2+p+1,f(p^k)=p^0+p^1+p^2+\cdots+p^k+\cdots+p^{2\cdot{k}} f(p)=p2+p+1,f(pk)=p0+p1+p2+⋯+pk+⋯+p2⋅k

void make()
{d_sum_pow_2[1]=1;for(int i=2;i<=maxn;i++){if(!prime[i]){prime[++prime[0]]=i; d_sum_pow_2[i]=i*i+i+1;//素数的话约数和是i^2+i+1.prime_pow_2_count[i]=d_sum_pow_2[i];//素数对应的最小质因子幂和就是i^2+i+1.}for(int j=1;j<=prime[0]&&prime[j]<=maxn/i;j++){int to=i*prime[j]; prime[to]=1;if(i%prime[j]==0){//如果不是互素的话,说明当前的i中至少含有一个prime[j].prime_pow_2_count[to]=prime_pow_2_count[i]*prime[j]*prime[j]+prime[j]+1;//先除去之前的,在重新乘上去即可.d_sum_pow_2[to]=d_sum_pow_2[i]/prime_pow_2_count[i]*prime_pow_2_count[to];break;}else {prime_pow_2_count[to]=prime[j]*prime[j]+prime[j]+1;d_sum_pow_2[to]=d_sum_pow_2[i]*d_sum_pow_2[prime[j]];//由于约数和函数是积性函数,所以互质的情况下等于直接相乘.}}}
}

6. f ( k ) = ∑ d ∣ k d ∗ μ ( d ) f(k)=\sum_{d|k}d*\mu(d) f(k)=∑d∣kd∗μ(d) :

f ( p ) = 1 − p f(p)=1-p f(p)=1−p , f ( p k ) = f ( p ) f(p^k)=f(p) f(pk)=f(p) .

void make()
{f[1]=1;for(int i=2;i<=maxn;i++){if(!prime[i]) prime[++prime[0]]=i,f[i]=1-i;for(int j=1;j<=prime[0]&&prime[j]<=maxn/i;j++){prime[i*prime[j]]=1;if(i%prime[j]==0){ f[i*prime[j]]=f[i]; break; } else f[i*prime[j]]=f[i]*f[prime[j]];}}
}

7. f ( k ) = ∑ d ∣ k d x ⋅ μ ( k d ) f(k) = \sum_{d|k}d^{x}\cdot\mu(\frac{k}{d}) f(k)=∑d∣kdx⋅μ(dk) :

f ( p ) = p x − 1 f(p)=p^{x}-1 f(p)=px−1 , f ( p k ) = f ( p k − 1 ) ⋅ p k f(p^k) = f(p^{k-1})\cdot{p^k} f(pk)=f(pk−1)⋅pk
具体推的过程可以先取 f ( p ) f(p) f(p) 观察出结果,再取 f ( p 2 ) f(p^2) f(p2) 和 f ( p ) f(p) f(p) 比较,从而得出结论

void make()
{f[1]=1;for(int i=2;i<=maxn;i++){if(!prime[i]){prime[++prime[0]]=i;g[i]=qpow(i,x);//记录p^xf[i]=g[i]-1;}for(int j=1;j<=prime[0]&&prime[j]<=maxn/i;j++){prime[i*prime[j]]=1;if(i%prime[j]==0){ f[i*prime[j]]=(f[i]*g[prime[j]])%mod; break; }else f[i*prime[j]]=(f[i]*f[prime[j]])%mod;}}
}

8. f ( k ) = ∑ d ∣ k φ ( d ) ⋅ μ ( k d ) f(k)=\sum_{d|k}\varphi(d)\cdot{\mu(\frac{k}{d})} f(k)=∑d∣kφ(d)⋅μ(dk) :

f ( p ) = p − 2 f(p) = p-2 f(p)=p−2 , f ( p k ) = p k + p k − 2 − 2 ⋅ p k − 1 f(p^k) = p^k+p^{k-2}-2\cdot{p^{k-1}} f(pk)=pk+pk−2−2⋅pk−1

void make()
{phimu[1]=1;for(int i=2;i<=maxn;i++){if(!prime[i]){prime[++prime[0]]=i;low[i]=i; phimu[i]=i-2;//low数组代表i的最小质因子乘积.}for(int j=1;j<=prime[0]&&prime[j]<=maxn/i;j++){int to=i*prime[j]; prime[to]=1;if(i%prime[j]==0){low[to]=low[i]*prime[j];if(low[i]==i){//如果当前这个合数是一个质因子的幂的形式,单独讨论.(也可以直接在下面讨论)if(i==prime[j]) phimu[to]=prime[j]*prime[j]+1-2*prime[j];//单独讨论为2的情况.else phimu[to]=phimu[i]*prime[j];}else phimu[to]=phimu[i/low[i]]*phimu[low[i]*prime[j]];//将最小质因子部分分割出去.break;}else{low[to]=prime[j];phimu[to]=phimu[i]*phimu[prime[j]];//互质就直接相乘.}}}
}

9. x ∣ i k , x = ∏ p i q i x|i^k,x=\prod{p_i}^{q_i} x∣ik,x=∏piqi ,令 f k ( x ) = ∏ p i ⌈ q i k ⌉ f_k(x)=\prod{p_i^{\lceil\frac{qi}{k}\rceil}} fk(x)=∏pi⌈kqi⌉ .

比如求 ∑ i = 1 A [ d ∣ i k ] \sum_{i=1}^A[d|i^k] ∑i=1A[d∣ik] ,那么答案就等于 ⌊ A f k ( d ) ⌋ \lfloor\frac{A}{f_k(d)}\rfloor ⌊fk(d)A⌋ .

可以发现 k = 1 k=1 k=1 的时候, f 1 ( x ) = x f_1(x) = x f1(x)=x ,下面给出 f 2 ( x ) , f 3 ( x ) f_2(x),f_3(x) f2(x),f3(x) 的线性筛代码:

void make()
{f2[1]=f3[1]=1;for(int i=2;i<=maxn;i++){if(!prime[i]){prime[++prime[0]]=i;low[i]=i;//low数组代表i的最小质因子乘积p^k.pow_cnt[i]=1;//pow_cnt记录i的最小质因子的幂.f2[i]=i; f3[i]=i;}for(int j=1;j<=prime[0]&&prime[j]<=maxn/i;j++){int to=i*prime[j];  prime[to]=1;if(i%prime[j]==0){low[to]=low[i]*prime[j];  pow_cnt[to]=pow_cnt[i]+1;//如果当前这个合数是一个质因子的幂的形式,单独讨论.(也可以直接在下面讨论)if(low[i]==i){f2[to]=f2[i];  f3[to]=f3[i];if(pow_cnt[to]%2==1) f2[to]*=prime[j];//如果恰好多1说明要加1if(pow_cnt[to]%3==1) f3[to]*=prime[j];}else{f2[to]=f2[i/low[i]]*f2[low[i]*prime[j]];//将最小质因子部分分割出去.f3[to]=f3[i/low[i]]*f3[low[i]*prime[j]];}break;}else{low[to]=prime[j];  pow_cnt[to]=1;f2[to]=f2[i]*f2[prime[j]];//互质就直接相乘.f3[to]=f3[i]*f3[prime[j]];}}}
}

gcd ⁡ \gcd gcd 相关题目

题意:

给定 n n n , m m m , d d d 求 ∑ i = 1 n ∑ j = 1 m [ gcd ⁡ ( i , j ) = = d ] \sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)==d] ∑i=1n∑j=1m[gcd(i,j)==d] .

题解:

根据反演常用套路,设 :

f ( d ) f(d) f(d) 为 ∑ i = 1 n ∑ j = 1 m [ gcd ⁡ ( i , j ) = = d ] \sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)==d] ∑i=1n∑j=1m[gcd(i,j)==d] . F ( n ) F(n) F(n) 为 ∑ i = 1 n ∑ j = 1 m d ∣ gcd ⁡ ( i , j ) \sum_{i=1}^n\sum_{j=1}^m{d}|\gcd(i,j) ∑i=1n∑j=1md∣gcd(i,j) .

则: ans = f ( d ) f(d) f(d)

= ∑ d ∣ k μ ( k d ) ⋅ F ( k ) \sum_{d|k}\mu(\frac{k}{d})\cdot{F(k)} ∑d∣kμ(dk)⋅F(k)

可以观察出: 对答案有贡献的 k k k 均是 d d d 的倍数,而 d d d 的倍数是有上限的,因此考虑更换枚举项为 k d \frac{k}{d} dk .

= ∑ k = 1 m i n ( n d , m d ) μ ( k ) ⋅ F ( k ⋅ d ) \sum_{k=1}^{min(\frac{n}{d},\frac{m}{d})}\mu(k)\cdot{F(k\cdot{d})} ∑k=1min(dn,dm)μ(k)⋅F(k⋅d)

由于 F ( k ) = n k ⋅ m k F(k)=\frac{n}{k}\cdot\frac{m}{k} F(k)=kn⋅km. 考虑后面分块处理即可解决问题.

— P 3455 P3455 P3455

题意:

给定 T T T , n n n , m m m , T T T 次询问, 输出 ∑ i = 1 n ∑ j = 1 m [ gcd ⁡ ( i , j ) = = P r i m e ] \sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)==Prime] ∑i=1n∑j=1m[gcd(i,j)==Prime]

T ≤ 1 0 4 T\le{10^4} T≤104 , N , M ≤ 1 0 6 N,M\le 10^6 N,M≤106 .

题解:

根据反演常用套路,设 :

设: S S S 为质数集.

ans = ∑ p ∈ S ∑ i = 1 n ∑ j = 1 m [ gcd ⁡ ( i , j ) = = p ] \sum_{p \in S} \sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)==p] ∑p∈S∑i=1n∑j=1m[gcd(i,j)==p]

= ∑ p ∈ S f ( p ) \sum_{p \in S} f(p) ∑p∈Sf(p)

= ∑ p ∈ S ∑ p ∣ d μ ( d p ) ⋅ F ( d ) \sum_{p \in S} \sum_{p|d} \mu(\frac{d}{p})\cdot{F(d)} ∑p∈S∑p∣dμ(pd)⋅F(d) (一般把分块的部分和 μ \mu μ 函数分开,所以需要更换枚举项)

= ∑ p ∈ S ∑ d = 1 m i n ( n p , m p ) μ ( d ) ⋅ F ( d ⋅ p ) \sum_{p \in S} \sum_{d=1}^{min(\frac{n}{p},\frac{m}{p})}\mu(d)\cdot{F(d\cdot{p})} ∑p∈S∑d=1min(pn,pm)μ(d)⋅F(d⋅p) (由枚举 d d d 变成 d p \frac{d}{p} pd )

由于此时枚举 p p p 的部分在最外面无法预处理,所以更换枚举项,改成枚举 d ∗ p d*p d∗p.

= ∑ k = 1 m i n ( n , m ) F ( k ) ⋅ ∑ p ∣ k , p ∈ S μ ( k p ) \sum_{k=1}^{min(n,m)}F(k)\cdot\sum_{p|k,p \in S} \mu(\frac{k}{p}) ∑k=1min(n,m)F(k)⋅∑p∣k,p∈Sμ(pk)

此时容易发现后面一部分可以预处理处理.前一部分可以分块.

— P 2257 P2257 P2257

题意:

求: ∑ i = 1 n ∑ j = 1 n gcd ⁡ ( i , j ) \sum_{i=1}^n\sum_{j=1}^n\gcd(i,j) ∑i=1n∑j=1ngcd(i,j) , n ≤ 1 0 10 n\le 10^{10} n≤1010

题解:

对于两个 ∑ \sum ∑ 前后都是 n n n 的情况,通常将后面的 ∑ \sum ∑ 上限换成 i i i ,然后减去多余的部分.

ans = ( 2 ⋅ ∑ i = 1 n ∑ j = 1 i gcd ⁡ ( i , j ) ) − ∑ i = 1 n i (2\cdot\sum_{i=1}^n\sum_{j=1}^i\gcd(i,j) )-\sum_{i=1}^ni (2⋅∑i=1n∑j=1igcd(i,j))−∑i=1ni

设 ans ′ ^{'} ′ = ∑ i = 1 n ∑ j = 1 i gcd ⁡ ( i , j ) \sum_{i=1}^n\sum_{j=1}^i\gcd(i,j) ∑i=1n∑j=1igcd(i,j)

ans ′ ^{'} ′ = ∑ d = 1 n d ⋅ ∑ i = 1 n d ∑ j = 1 i [ gcd ⁡ ( i , j ) = = 1 ] \sum_{d=1}^nd\cdot\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^i [\gcd(i,j)==1] ∑d=1nd⋅∑i=1dn∑j=1i[gcd(i,j)==1]

此时容易发现 ∑ j = 1 i [ gcd ⁡ ( i , j ) = = 1 ] \sum_{j=1}^i[\gcd(i,j)==1] ∑j=1i[gcd(i,j)==1] 是 i i i 以内与 i i i 互质的数的个数 ,因此原式再次化简为:

= ∑ d = 1 n d ⋅ ∑ i = 1 n d φ ( i ) \sum_{d=1}^nd\cdot\sum_{i=1}^{\frac{n}{d}}\varphi(i) ∑d=1nd⋅∑i=1dnφ(i)

= ∑ i = 1 n φ ( i ) ⋅ ∑ d = 1 n i d \sum_{i=1}^n\varphi(i)\cdot\sum_{d=1}^{\frac{n}{i}}d ∑i=1nφ(i)⋅∑d=1ind

此时可用杜教筛处理出 ∑ i = 1 n φ ( i ) \sum_{i=1}^n\varphi(i) ∑i=1nφ(i) ,即可解决该题.

— 51 N o d 1237 51Nod 1237 51Nod1237

题意:

∑ i = 1 n ∑ j = 1 m [ gcd ⁡ ( i , j ) = = k ] [ t s u m ≤ P ] \sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)==k][tsum\leq{P}] ∑i=1n∑j=1m[gcd(i,j)==k][tsum≤P] (tsum为k的质数幂和,P为题目给定)

1 ≤ n , m ≤ 1 0 5 1\le{n,m}\le10^5 1≤n,m≤105, 0 ≤ P ≤ 1 0 5 0\le{P}\le10^5 0≤P≤105. Q次询问, Q ≤ 1 0 5 Q\le10^5 Q≤105.( 1的tsum为0 ).

题解:

用f(d)表示满足 d = gcd ⁡ ( i , j ) , 且 1 ≤ i ≤ n , 1 ≤ j ≤ m d=\gcd(i,j),且 1\le{i}\le{n},1\le{j}\le{m} d=gcd(i,j),且1≤i≤n,1≤j≤m的对数.

用F(d)表示满足 d ∣ gcd ⁡ ( i , j ) , 且 1 ≤ i ≤ n , 1 ≤ j ≤ m d|\gcd(i,j),且 1\le{i}\le{n},1\le{j}\le{m} d∣gcd(i,j),且1≤i≤n,1≤j≤m的对数.

可知: F ( d ) = ⌊ n d ⌋ F(d)=\lfloor\frac{n}{d}\rfloor F(d)=⌊dn⌋ ⋅ ⌊ m d ⌋ \cdot\lfloor\frac{m}{d}\rfloor ⋅⌊dm⌋ , f ( x ) = ∑ x ∣ d μ ( d x ) ⋅ F ( d ) f(x) = \sum_{x|d}\mu(\frac{d}{x})\cdot{F(d)} f(x)=∑x∣dμ(xd)⋅F(d).

设k为满足 t s u m ≤ P tsum\le{P} tsum≤P的数. 则枚举每一个k既是答案:

ans = ∑ k f ( k ) \sum_kf(k) ∑kf(k)

= ∑ k ∑ k ∣ d μ ( d k ) ⋅ F ( d ) \sum_k\sum_{k|d}\mu(\frac{d}{k})\cdot{F(d)} ∑k∑k∣dμ(kd)⋅F(d)

= ∑ d = 1 m i n ( n , m ) F ( d ) ⋅ ∑ k ∣ d μ ( d k ) \sum_{d=1}^{min(n,m)}F(d)\cdot\sum_{k|d}\mu(\frac{d}{k}) ∑d=1min(n,m)F(d)⋅∑k∣dμ(kd) (更换枚举项)

此时发现后面的可以线性筛出来后做前缀和即可.由于tsum最多不超过20.所以线性筛的时候记录

一下即可.

const int maxn = 5e5+7;
int prime[maxn+5],mu[maxn+5],pow_cnt[maxn+5];//pow_cnt记录i的质因子幂和.(出现+1即可).
long long sum[21][maxn+5];
void init()
{make_mu();for(int i=1;i<=maxn;i++)for(int j=i;j<=maxn;j+=i)sum[pow_cnt[i]][j]+=mu[j/i];//质因子个数为pow_cnt[i],能贡献的所有j.for(int i=1;i<=20;i++)for(int j=1;j<=maxn;j++)sum[i][j]+=sum[i-1][j];for(int i=0;i<=20;i++)for(int j=1;j<=maxn;j++)sum[i][j]+=sum[i][j-1];
}
int main()
{scanf("%d",&t);while(t--){scanf("%d%d%d",&n,&m,&p);if(p>20){printf("%lld\n",1LL*n*m);continue;}long long ans=0;for(int l=1,r;l<=min(n,m);l=r+1){r=min(n/(n/l),m/(m/l));ans+=1LL*(n/l)*(m/l)*(sum[p][r]-sum[p][l-1]);}printf("%lld\n",ans);}
}

— h d u 4746 hdu4746 hdu4746

l c m lcm lcm 相关题目

题意:

求 ∑ i = 1 n ∑ j = 1 m L C M ( i , j ) \sum_{i=1}^n\sum_{j=1}^mLCM(i,j) ∑i=1n∑j=1mLCM(i,j) , n , m ≤ 1 0 7 n,m\le 10^7 n,m≤107 .

题解:

由于 L C M ( i , j ) = i ⋅ j gcd ⁡ ( i , j ) LCM(i,j) = \frac{i\cdot{j}}{\gcd(i,j)} LCM(i,j)=gcd(i,j)i⋅j .

ans = ∑ i = 1 n ∑ j = 1 m i ⋅ j gcd ⁡ ( i , j ) \sum_{i=1}^n\sum_{j=1}^m\frac{i\cdot{j}}{\gcd(i,j)} ∑i=1n∑j=1mgcd(i,j)i⋅j

= ∑ d = 1 m i n ( n , m ) ∑ i = 1 n d ∑ j = 1 m d i ⋅ j ⋅ d ⋅ [ gcd ⁡ ( i , j ) = = 1 ] \sum_{d=1}^{min(n,m)}\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}i\cdot{j}\cdot{d}\cdot[\gcd(i,j)==1] ∑d=1min(n,m)∑i=1dn∑j=1dmi⋅j⋅d⋅[gcd(i,j)==1] (考虑枚举 gcd ⁡ ( i , j ) \gcd(i,j) gcd(i,j))

= ∑ d = 1 m i n ( n , m ) ∑ i = 1 n d ∑ j = 1 m d i ⋅ j ⋅ d ⋅ ∑ k ∣ gcd ⁡ ( i , j ) μ ( k ) \sum_{d=1}^{min(n,m)}\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}i\cdot{j}\cdot{d}\cdot \sum_{k|\gcd(i,j)}\mu(k) ∑d=1min(n,m)∑i=1dn∑j=1dmi⋅j⋅d⋅∑k∣gcd(i,j)μ(k) (考虑将 [ gcd ⁡ ( i , j ) = = 1 ] [\gcd(i,j)==1] [gcd(i,j)==1] 更换为 μ \mu μ)

= ∑ d = 1 min ⁡ ( n , m ) d ⋅ ∑ k = 1 min ⁡ ( n d , m d ) k 2 ⋅ μ ( k ) ⋅ ∑ i = 1 n k ⋅ d i ⋅ ∑ j = 1 m k ⋅ d j \sum_{d=1}^{\min(n,m)}{d}\cdot\sum_{k=1}^{\min(\frac{n}{d},\frac{m}{d})}{k^2}\cdot\mu(k)\cdot\sum_{i=1}^{\frac{n}{k\cdot{d}}}{i}\cdot\sum_{j=1}^{\frac{m}{k\cdot{d}}}{j} ∑d=1min(n,m)d⋅∑k=1min(dn,dm)k2⋅μ(k)⋅∑i=1k⋅dni⋅∑j=1k⋅dmj (考虑枚举 k)

此时枚举 d d d 即可过题. 但还可以通过更换枚举项将复杂度再次降低.

由于 ∑ i = 1 x i \sum_{i=1}^{x}i ∑i=1xi 可以 O ( 1 ) O(1) O(1) 的计算出,所以我们用 f ( x ) f(x) f(x) 来代表 ∑ i = 1 x i \sum_{i=1}^xi ∑i=1xi .

= ∑ d = 1 m i n ( n , m ) f ( n d ) ⋅ f ( m d ) ⋅ d ⋅ ∑ k ∣ d k ⋅ μ ( k ) \sum_{d=1}^{min(n,m)}f(\frac{n}{d})\cdot{f(\frac{m}{d})}\cdot{d}\cdot\sum_{k|d}k\cdot\mu(k) ∑d=1min(n,m)f(dn)⋅f(dm)⋅d⋅∑k∣dk⋅μ(k)

考虑预处理出 d ⋅ ∑ k ∣ d k ⋅ μ ( k ) d\cdot\sum_{k|d}k\cdot\mu(k) d⋅∑k∣dk⋅μ(k) .设 g ( d ) = ∑ k ∣ d k ⋅ μ ( k ) g(d)=\sum_{k|d}k\cdot\mu(k) g(d)=∑k∣dk⋅μ(k) .由于 g ( d ) g(d) g(d) 是积性函数,所以可以线性筛出.

最后做次前缀和即可解决这道题.

— P 1829 P1829 P1829

题意:

求: ∑ i = 1 n ∑ j = 1 n L C M ( i , j ) \sum_{i=1}^n\sum_{j=1}^nLCM(i,j) ∑i=1n∑j=1nLCM(i,j) , n ≤ 1 0 10 n\le 10^{10} n≤1010

题解:

对于两个 ∑ \sum ∑ 前后都是 n n n 的情况,通常将后面的 ∑ \sum ∑ 上限换成 i i i ,然后减去多余的部分.

ans = ( 2 ⋅ ∑ i = 1 n ∑ j = 1 i i ⋅ j gcd ⁡ ( i , j ) ) − ∑ i = 1 n i (2\cdot\sum_{i=1}^n\sum_{j=1}^i\frac{i\cdot{j}}{\gcd(i,j)} )-\sum_{i=1}^ni (2⋅∑i=1n∑j=1igcd(i,j)i⋅j)−∑i=1ni

设 ans ′ ^{'} ′ = ∑ i = 1 n ∑ j = 1 i i ⋅ j gcd ⁡ ( i , j ) \sum_{i=1}^n\sum_{j=1}^i\frac{i\cdot{j}}{\gcd(i,j)} ∑i=1n∑j=1igcd(i,j)i⋅j

ans ′ ^{'} ′ = ∑ d = 1 n d ⋅ ∑ i = 1 n d ∑ j = 1 i i ⋅ j ⋅ [ gcd ⁡ ( i , j ) = = 1 ] \sum_{d=1}^nd\cdot\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^ii\cdot{j}\cdot [\gcd(i,j)==1] ∑d=1nd⋅∑i=1dn∑j=1ii⋅j⋅[gcd(i,j)==1]

此时容易发现 ∑ j = 1 i j ⋅ [ gcd ⁡ ( i , j ) = = 1 ] \sum_{j=1}^ij\cdot[\gcd(i,j)==1] ∑j=1ij⋅[gcd(i,j)==1] 是 i i i 以内与 i i i 互质的数之和 ,因此原式再次化简为:

= ∑ d = 1 n d ⋅ ∑ i = 1 n d i 2 ⋅ φ ( i ) 2 \sum_{d=1}^nd\cdot\sum_{i=1}^{\frac{n}{d}}\frac{i^2\cdot\varphi(i)}{2} ∑d=1nd⋅∑i=1dn2i2⋅φ(i)

= ∑ i = 1 n i 2 ⋅ φ ( i ) 2 ∑ d = 1 n i d \sum_{i=1}^n\frac{i^2\cdot\varphi(i)}{2}\sum_{d=1}^{\frac{n}{i}}d ∑i=1n2i2⋅φ(i)∑d=1ind

此时可用杜教筛处理出 ∑ i = 1 n i 2 ⋅ φ ( i ) 2 \sum_{i=1}^n\frac{i^2\cdot\varphi(i)}{2} ∑i=1n2i2⋅φ(i) ,即可解决该题.

— 51 N o d 1238 51Nod1238 51Nod1238

题意:

求满足 a ≤ l c m ( x , y ) ≤ b {a}\le { lcm(x,y) } \le {b} a≤lcm(x,y)≤b 且 x ≤ y x\le{y} x≤y 的二元组 ( x , y ) (x,y) (x,y) 的数量. 1 ≤ a , b ≤ 1 0 11 1\le{a,b}\le{10^{11}} 1≤a,b≤1011

题解:

容易发现可以答案可以转化为求满足 1 ≤ l c m ( x , y ) ≤ b 1\le{lcm(x,y)}\le{b} 1≤lcm(x,y)≤b 的数量减去 1 ≤ l c m ( x , y ) ≤ ( a − 1 ) 1\le{lcm(x,y)}\le{(a-1)} 1≤lcm(x,y)≤(a−1) 的数量.

问题转化为求满足 1 ≤ l c m ( x , y ) ≤ n 1\le{lcm(x,y)}\le{n} 1≤lcm(x,y)≤n 的数量,我们先不考虑 x ≤ y x\le{y} x≤y ,算出这种情况下的答案再去掉重复的即可.

因此要求的式子变成了: ∑ i = 1 n ∑ j = 1 n [ l c m ( i , j ) ≤ n ] \sum_{i=1}^n\sum_{j=1}^n[lcm(i,j)\le{n}] ∑i=1n∑j=1n[lcm(i,j)≤n]

= ∑ d = 1 n ∑ i = 1 n d ∑ j = 1 n d [ i ⋅ j ⋅ d ≤ n ] ⋅ [ gcd ⁡ ( i , j ) = = 1 ] \sum_{d=1}^n\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{n}{d}}[i\cdot{j}\cdot{d}\le{n}]\cdot[\gcd(i,j)==1] ∑d=1n∑i=1dn∑j=1dn[i⋅j⋅d≤n]⋅[gcd(i,j)==1]

= ∑ d = 1 n ∑ k = 1 n d μ ( k ) ⋅ ∑ i = 1 n k ⋅ d ∑ j = 1 n k ⋅ d [ i ⋅ j ⋅ d ⋅ k 2 ≤ n ] \sum_{d=1}^n\sum_{k=1}^{\frac{n}{d}}\mu(k)\cdot\sum_{i=1}^{\frac{n}{k\cdot{d}}}\sum_{j=1}^{\frac{n}{k\cdot{d}}}[i\cdot{j}\cdot{d}\cdot{k^2}\le{n}] ∑d=1n∑k=1dnμ(k)⋅∑i=1k⋅dn∑j=1k⋅dn[i⋅j⋅d⋅k2≤n]

此时更换 k k k 和 d d d 的位置,同时将 k 2 k^2 k2 移到右边可得:

= ∑ k = 1 n ∑ d = 1 n k 2 ∑ i = 1 n k 2 ⋅ d ∑ j = 1 n k 2 ⋅ d [ i ⋅ j ⋅ d ≤ n k 2 ] \sum_{k=1}^{\sqrt{n}}\sum_{d=1}^{\frac{n}{k^2}}\sum_{i=1}^{\frac{n}{k^2\cdot{d}}}\sum_{j=1}^{\frac{n}{k^2\cdot{d}}}[i\cdot{j}\cdot{d}\le\frac{n}{k^2}] ∑k=1n ∑d=1k2n∑i=1k2⋅dn∑j=1k2⋅dn[i⋅j⋅d≤k2n]

观察发现后面一部分求的是形如 [ a ⋅ b ⋅ c ≤ n ] [a\cdot{b}\cdot{c}\le{n}] [a⋅b⋅c≤n] 的东西.

因此令 a ≤ b ≤ c a\le{b}\le{c} a≤b≤c ,那么 a a a 只需要枚举到 n 1 3 n^{\frac{1}{3}} n31 ,然后 b b b 枚举到 ⌊ n a ⌋ \sqrt{\lfloor\frac{n}{a}\rfloor} ⌊an⌋ , c c c 的范围可以直接算出.

然后统计三个数相同,两个数相同,三个数都不同的情况即可解决该题.

long long cal(long long n)//计算1~n中LCM(i,j)<=n的对数.
{if(!n) return 0;long long res=0;for(int k=1;1LL*k*k<=n;k++){if(mu[k]==0) continue;long long x=n/(1LL*k*k);long long now=0;//计算a*b*c<=x的对数.for(int i=1;1LL*i*i*i<=x;i++){//枚举第一位.for(int j=i+1;1LL*j*j*i<=x;j++)//枚举第二位now+=1LL*(x/(1LL*i*j)-j)*6+3;//a<b<c时累计num*6,a<b=c时累计3.now+=1LL*(x/(1LL*i*i)-i)*3+1;//a=b<c时累计num*3,a=b=c时累计1.}if(mu[k]==1) res+=now;else res-=now;}return (res+n)>>1;//程序计算的是无顺序的,答案要求有顺序,所以(ans+n)/2;
}

— 51 N o d 1222 51Nod1222 51Nod1222

约数个数函数相关题目

题意:

求 ∑ i = 1 n ∑ j = 1 m d ( i ⋅ j ) \sum_{i=1}^n\sum_{j=1}^md(i\cdot{j}) ∑i=1n∑j=1md(i⋅j) n , m ≤ 1 0 5 n,m\le{10^5} n,m≤105

题解:

a n s = ∑ i = 1 n ∑ j = 1 m ∑ x ∣ i ∑ y ∣ j [ gcd ⁡ ( x , y ) = = 1 ] ans = \sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}[\gcd(x,y)==1] ans=∑i=1n∑j=1m∑x∣i∑y∣j[gcd(x,y)==1]

= ∑ x = 1 n ∑ y = 1 m n x ⋅ m y ⋅ [ gcd ⁡ ( x , y ) = = 1 ] = \sum_{x=1}^n\sum_{y=1}^m\frac{n}{x}\cdot\frac{m}{y}\cdot[\gcd(x,y)==1] =∑x=1n∑y=1mxn⋅ym⋅[gcd(x,y)==1] (由上一步更换枚举项得到)

= ∑ x = 1 n ∑ y = 1 m n x ⋅ m y ⋅ ∑ k ∣ gcd ⁡ ( x , y ) μ ( k ) = \sum_{x=1}^n\sum_{y=1}^m\frac{n}{x}\cdot\frac{m}{y}\cdot\sum_{k|\gcd(x,y)}\mu(k) =∑x=1n∑y=1mxn⋅ym⋅∑k∣gcd(x,y)μ(k)

= ∑ k = 1 m i n ( n , m ) μ ( k ) ⋅ ∑ x = 1 n k n k ⋅ x ⋅ ∑ y = 1 m k m k ⋅ y = \sum_{k=1}^{min(n,m)}\mu(k)\cdot\sum_{x=1}^{\frac{n}{k}}\frac{n}{k\cdot{x}}\cdot\sum_{y=1}^{\frac{m}{k}}\frac{m}{k\cdot{y}} =∑k=1min(n,m)μ(k)⋅∑x=1knk⋅xn⋅∑y=1kmk⋅ym

可以发现后一部分可以分块处理,因此问题得到解决.

— B Z O J 3994 BZOJ3994 BZOJ3994

题意:

求 ∑ i = 1 n σ ( i ) \sum_{i=1}^n\sigma(i) ∑i=1nσ(i) , n < 2 63 n\lt2^{63} n<263 , 1 0 5 10^5 105 组数据 , 15 s 15s 15s . (神仙题)
题目给的是 σ \sigma σ , 但求的是约数个数.

题解:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+7;
typedef long long ll;
typedef __int128 lll;
int t;
ll n;
struct Node{ll x,y;Node(ll _x=0,ll _y=0):x(_x),y(_y){}inline Node operator + (const Node &B){return Node(x+B.x,y+B.y);}
}S[maxn];
int top=0;
inline bool inner(ll x,ll y){return n<x*y;}
inline bool steep(ll x,Node v){return (lll)n*v.x<=(lll)x*x*v.y; }
lll solve()
{int i,crn = cbrt(n);//获取n的立方根.ll srn = sqrt(n);//获取n的平方根.ll x = n/srn;ll y = srn+1;lll res=0;struct Node L,R,M;S[++top]=(Node(1,0));S[++top]=(Node(1,1));while(true){for(L=S[top--];inner(x+L.x,y-L.y);x+=L.x,y-=L.y)res+=x*L.y+(L.y+1)*(L.x-1)/2;if(y<=crn) break;for(R=S[top];!inner(x+R.x,y-R.y);R=S[--top]) L=R;while(M=(L+R),1){if(inner(x+M.x,y-M.y)) S[++top]=R=M;else{if(steep(x+M.x,R))  break;L=M;}}}for(i=1;i<y;i++) res+=n/i;return res*2-srn*srn;
}
inline void print(lll x)
{static char buf[36];if(!x) {putchar(48); return ;}int i=0;for(;x;buf[++i]=x%10|48,x/=10);for(;i;--i) putchar(buf[i]);
}
int main()
{scanf("%d",&t);while(t--){scanf("%lld",&n);print(solve());putchar(10);}return 0;
}

— S P O J SPOJ SPOJ D I V C N T 1 DIVCNT1 DIVCNT1

题意:

求 ∑ i = 1 n d ( i 2 ) \sum_{i=1}^nd(i^2) ∑i=1nd(i2) n ≤ 1 0 12 n\le{10^{12}} n≤1012

题解:

容易发现我们对于 d ( i 2 ) d(i^2) d(i2) 没办法直接处理,所以对于 d ( n 2 ) d(n^2) d(n2) ,我们考虑那些 n 2 n^2 n2 有的因子,而 n n n 没有的因子,可以知道,对于 n = p 1 q 1 ⋅ p 2 q 2 ⋯ p t q t n=p_1^{q_1}\cdot{p_2}^{q_2}\cdots{p_t}^{q_t} n=p1q1⋅p2q2⋯ptqt ,每一个 n n n 有的约数对应质因子指数上分别加上 0 0 0 或 q i q_i qi ,可以构成一个 n 2 n^2 n2 的因子.

即: d ( n 2 ) = ∑ d ∣ n 2 w ( d ) d(n^2)=\sum_{d|n}2^{w(d)} d(n2)=∑d∣n2w(d) ( w ( d ) w(d) w(d)表示 d d d 的不同质因子个数 ) .

a n s = ∑ i = 1 n ∑ d ∣ n 2 w ( d ) ans = \sum_{i=1}^n\sum_{d|n}2^{w(d)} ans=∑i=1n∑d∣n2w(d)

考虑 2 w ( d ) 2^{w(d)} 2w(d) , 本质上是 d d d 的所有约数中无平方因数的个数,他们有一个特点, μ \mu μ 要么是 − 1 -1 −1要么是 1 1 1 .

= ∑ i = 1 n ∑ d ∣ i ∑ k ∣ d μ 2 ( k ) = \sum_{i=1}^n\sum_{d|i}\sum_{k|d}\mu^2(k) =∑i=1n∑d∣i∑k∣dμ2(k)

= ∑ i = 1 n ∑ k ∣ i μ 2 ( k ) ⋅ d ( i k ) = \sum_{i=1}^n\sum_{k|i}\mu^2(k)\cdot{d(\frac{i}{k})} =∑i=1n∑k∣iμ2(k)⋅d(ki)

= ∑ k = 1 n μ 2 ( k ) ⋅ ∑ i = 1 n k d ( i ) = \sum_{k=1}^n\mu^2(k)\cdot\sum_{i=1}^{\frac{n}{k}}d(i) =∑k=1nμ2(k)⋅∑i=1knd(i)

发现 ∑ k = 1 n μ 2 ( k ) \sum_{k=1}^n\mu^2(k) ∑k=1nμ2(k) 等于 1 1 1 ~ n n n 中无平方因子数的个数,等于 ∑ i = 1 n μ ( i ) ⋅ n i 2 \sum_{i=1}^{\sqrt{n}}\mu(i)\cdot{\frac{n}{i^2}} ∑i=1n μ(i)⋅i2n

因此分块即可解决此题.

— S P O J SPOJ SPOJ D I V C N T 2 DIVCNT2 DIVCNT2

约数和函数相关题目

题意:

求 ∑ i = 1 n ∑ j = 1 n σ ( i ⋅ j ) \sum_{i=1}^n\sum_{j=1}^n\sigma(i\cdot{j}) ∑i=1n∑j=1nσ(i⋅j) n ≤ 1 0 9 n\le{10^9} n≤109

题解:

a n s = ∑ i = 1 n ∑ j = 1 n ∑ x ∣ i ∑ y ∣ j x ⋅ j y ⋅ [ gcd ⁡ ( x , y ) = = 1 ] ans = \sum_{i=1}^n\sum_{j=1}^n\sum_{x|i}\sum_{y|j}x\cdot{\frac{j}{y}}\cdot[\gcd(x,y)==1] ans=∑i=1n∑j=1n∑x∣i∑y∣jx⋅yj⋅[gcd(x,y)==1]

= ∑ x = 1 n ∑ y = 1 n x ⋅ ∑ j = 1 n y j ⋅ [ gcd ⁡ ( x , y ) = = 1 ] = \sum_{x=1}^n\sum_{y=1}^nx\cdot\sum_{j=1}^{\frac{n}{y}}j\cdot[\gcd(x,y)==1] =∑x=1n∑y=1nx⋅∑j=1ynj⋅[gcd(x,y)==1]

= ∑ x = 1 n ∑ y = 1 n x ⋅ ∑ j = 1 n y j ⋅ ∑ k ∣ gcd ⁡ ( x , y ) μ ( k ) =\sum_{x=1}^n\sum_{y=1}^nx\cdot\sum_{j=1}^{\frac{n}{y}}j\cdot\sum_{k|\gcd(x,y)}\mu(k) =∑x=1n∑y=1nx⋅∑j=1ynj⋅∑k∣gcd(x,y)μ(k)

= ∑ k = 1 n k ⋅ μ ( k ) ⋅ ∑ x = 1 n k x ⋅ ∑ y = 1 n k ∑ j = 1 n k ⋅ y j = \sum_{k=1}^nk\cdot\mu(k)\cdot\sum_{x=1}^{\frac{n}{k}}x\cdot\sum_{y=1}^{\frac{n}{k}}\sum_{j=1}^{\frac{n}{k\cdot{y}}}j =∑k=1nk⋅μ(k)⋅∑x=1knx⋅∑y=1kn∑j=1k⋅ynj

由于 ∑ i = 1 n i ⋅ ⌊ n i ⌋ = ∑ i = 1 n ∑ j = 1 n i j = ∑ i = 1 n σ ( i ) \sum_{i=1}^ni\cdot{\lfloor\frac{n}{i}\rfloor}=\sum_{i=1}^n\sum_{j=1}^{\frac{n}{i}}j=\sum_{i=1}^n\sigma(i) ∑i=1ni⋅⌊in⌋=∑i=1n∑j=1inj=∑i=1nσ(i)

所以: = ∑ k = 1 n k ⋅ μ ( k ) ⋅ ( ∑ i = 1 n k σ ( i ) ) 2 = \sum_{k=1}^nk\cdot\mu(k)\cdot(\sum_{i=1}^{\frac{n}{k}}\sigma(i))^2 =∑k=1nk⋅μ(k)⋅(∑i=1knσ(i))2

因此分块加杜教筛即可解决该题. (后面的部分可以用杜教筛的思想预处理前 n 2 3 n^{\frac{2}{3}} n32 项,然后分块出后 n 1 3 n^{\frac{1}{3}} n31 项)

— 51 N o d 1220 51Nod1220 51Nod1220

题意:

求 ∑ i = 1 n ∑ j = 1 n m a x ( i , j ) ⋅ σ ( i ⋅ j ) \sum_{i=1}^n\sum_{j=1}^nmax(i,j)\cdot\sigma(i\cdot{j}) ∑i=1n∑j=1nmax(i,j)⋅σ(i⋅j) n ≤ 1 0 6 n\le{10^6} n≤106 , 5 ⋅ 1 0 4 5\cdot10^4 5⋅104 组数据.

题解:

易得: a n s = 2 ⋅ ∑ i = 1 n ∑ j = 1 i i ⋅ σ ( i ⋅ j ) − ∑ i = 1 n i ⋅ σ ( i 2 ) ans = 2\cdot\sum_{i=1}^n\sum_{j=1}^ii\cdot\sigma(i\cdot{j})-\sum_{i=1}^ni\cdot\sigma(i^2) ans=2⋅∑i=1n∑j=1ii⋅σ(i⋅j)−∑i=1ni⋅σ(i2)

可以发现后面一部分是可以线性筛出来的.所以式子变成:

a n s ′ = ∑ i = 1 n ∑ j = 1 i i ⋅ σ ( i ⋅ j ) ans^{'} = \sum_{i=1}^n\sum_{j=1}^ii\cdot\sigma(i\cdot{j}) ans′=∑i=1n∑j=1ii⋅σ(i⋅j)

= ∑ i = 1 n ∑ j = 1 i i ⋅ ∑ x ∣ i ∑ y ∣ j x ⋅ j y ⋅ [ gcd ⁡ ( x , y ) = = 1 ] = \sum_{i=1}^n\sum_{j=1}^ii\cdot\sum_{x|i}\sum_{y|j}x\cdot\frac{j}{y}\cdot[\gcd(x,y)==1] =∑i=1n∑j=1ii⋅∑x∣i∑y∣jx⋅yj⋅[gcd(x,y)==1]

= ∑ x = 1 n x 2 ⋅ ∑ i = 1 x i i ⋅ ∑ y = 1 i ⋅ x ∑ j = 1 i ⋅ x y j ⋅ [ gcd ⁡ ( x , y ) = = 1 ] = \sum_{x=1}^nx^2\cdot\sum_{i=1}^{\frac{x}{i}}i\cdot\sum_{y=1}^{i\cdot{x}}\sum_{j=1}^{\frac{i\cdot{x}}{y}}j\cdot[\gcd(x,y)==1] =∑x=1nx2⋅∑i=1ixi⋅∑y=1i⋅x∑j=1yi⋅xj⋅[gcd(x,y)==1]

= ∑ x = 1 n x 2 ⋅ ∑ i = 1 x i i ⋅ ∑ y = 1 i ⋅ x σ ( y ) ⋅ [ gcd ⁡ ( x , y ) = = 1 ] =\sum_{x=1}^nx^2\cdot\sum_{i=1}^{\frac{x}{i}}i\cdot\sum_{y=1}^{i\cdot{x}}\sigma(y)\cdot[\gcd(x,y)==1] =∑x=1nx2⋅∑i=1ixi⋅∑y=1i⋅xσ(y)⋅[gcd(x,y)==1]

= ∑ k = 1 n k 2 ⋅ μ ( k ) ⋅ ∑ x = 1 n k x 2 ⋅ ∑ i = 1 n k ⋅ x i ⋅ ∑ y = 1 i ⋅ x σ ( y ) =\sum_{k=1}^nk^2\cdot\mu(k)\cdot\sum_{x=1}^{\frac{n}{k}}x^2\cdot\sum_{i=1}^{\frac{n}{k\cdot{x}}}i\cdot\sum_{y=1}^{i\cdot{x}}\sigma(y) =∑k=1nk2⋅μ(k)⋅∑x=1knx2⋅∑i=1k⋅xni⋅∑y=1i⋅xσ(y)

= ∑ k = 1 n k 2 ⋅ μ ( k ) ∑ i = 1 n k i ⋅ σ ( i ) ⋅ ∑ j = 1 i σ ( j ) =\sum_{k=1}^nk^2\cdot\mu(k)\sum_{i=1}^{\frac{n}{k}}i\cdot\sigma(i)\cdot\sum_{j=1}^i\sigma(j) =∑k=1nk2⋅μ(k)∑i=1kni⋅σ(i)⋅∑j=1iσ(j) (由上一步更换枚举项可得)

此时可以分块做,但由于数据组数过多,令 T = i ⋅ k T=i\cdot{k} T=i⋅k 可以再次变换:

= ∑ T = 1 n ∑ k ∣ T T ⋅ k ⋅ μ ( k ) ⋅ σ ( T k ) ⋅ ∑ i = 1 T k σ ( i ) =\sum_{T=1}^n\sum_{k|T}T\cdot{k}\cdot\mu(k)\cdot\sigma(\frac{T}{k})\cdot\sum_{i=1}^{\frac{T}{k}}\sigma(i) =∑T=1n∑k∣TT⋅k⋅μ(k)⋅σ(kT)⋅∑i=1kTσ(i)

此时可以 n ⋅ ln ⁡ n n\cdot{\ln{n}} n⋅lnn 预处理出解然后 O ( 1 ) O(1) O(1) 的输出答案.

— 51 N o d 1584 51Nod1584 51Nod1584

欧拉函数相关题目

题意:

给定 n , m n,m n,m ,求 ∑ i = 1 n ∑ j = 1 m φ ( i ⋅ j ) \sum_{i=1}^n\sum_{j=1}^m\varphi(i\cdot{j}) ∑i=1n∑j=1mφ(i⋅j) , n ≤ 1 0 5 n\le{10^5} n≤105 , m ≤ 1 0 9 m\le{10^9} m≤109 .

题解:

首先观察到 n n n 的范围较小,因此考虑令 S ( n , m ) = ∑ i = 1 m φ ( n ⋅ i ) S(n,m) = \sum_{i=1}^m\varphi(n\cdot{i}) S(n,m)=∑i=1mφ(n⋅i) , 则 $ans $ = ∑ i = 1 n S ( i , m ) \sum_{i=1}^nS(i,m) ∑i=1nS(i,m)

现在考虑化简 ∑ i = 1 m φ ( n ⋅ i ) \sum_{i=1}^m\varphi(n\cdot{i}) ∑i=1mφ(n⋅i) . 我们发现没有直接的公式可以化简 φ ( n ⋅ i ) \varphi(n\cdot{i}) φ(n⋅i) , 因此考虑从 φ ( x ) \varphi(x) φ(x) 的定义考虑.

由于 φ ( x ) \varphi(x) φ(x) = = = p 1 q 1 ⋅ p 2 q 2 ⋅ p 3 q 3 ⋯ p t q t ⋅ ( 1 − 1 p 1 ) ⋅ ( 1 − 1 p 2 ) ⋅ ( 1 − 1 p 3 ) ⋯ ( 1 − 1 p t ) p_1^{q_{1}}\cdot{p_2^{q_{2}}}\cdot{p_3^{q_{3}}}\cdots{p_t^{q_{t}}}\cdot{(1-\frac{1}{p_1})}\cdot{(1-\frac{1}{p_2})}\cdot{(1-\frac{1}{p_3})}\cdots(1-\frac{1}{p_t}) p1q1⋅p2q2⋅p3q3⋯ptqt⋅(1−p11)⋅(1−p21)⋅(1−p31)⋯(1−pt1)

= = = p 1 q 1 − 1 ⋅ p 2 q 2 − 1 ⋅ p 3 q 3 − 1 ⋯ p t q t − 1 ⋅ ( p 1 − 1 ) ⋅ ( p 2 − 1 ) ⋅ ( p 3 − 1 ) ⋯ ( p t − 1 ) p_1^{q_1-1}\cdot{p_2^{q_2-1}}\cdot{p_3^{q_3-1}}\cdots{p_t^{q_t-1}}\cdot(p_1-1)\cdot(p_2-1)\cdot(p_3-1)\cdots(p_t-1) p1q1−1⋅p2q2−1⋅p3q3−1⋯ptqt−1⋅(p1−1)⋅(p2−1)⋅(p3−1)⋯(pt−1)

所以我们可以把 x x x 表示成 y ⋅ w y\cdot{w} y⋅w ,分别对应上面的前一部分和后一部分.因此,原式可以化简成:

= = = y ⋅ ∑ i = 1 m φ ( w ⋅ i ) y\cdot\sum_{i=1}^m\varphi(w\cdot{i}) y⋅∑i=1mφ(w⋅i)

此时再考虑将 w w w 和 i i i 的公因子都放到 w w w 上:

= = = y ⋅ ∑ i = 1 m φ ( w gcd ⁡ ( w , i ) ⋅ i ⋅ gcd ⁡ ( w , i ) ) y\cdot\sum_{i=1}^m\varphi(\frac{w}{\gcd(w,i)}\cdot{i}\cdot{\gcd(w,i)}) y⋅∑i=1mφ(gcd(w,i)w⋅i⋅gcd(w,i))

= = = y ⋅ ∑ i = 1 m φ ( w gcd ⁡ ( w , i ) ) ⋅ φ ( i ⋅ gcd ⁡ ( w , i ) ) y\cdot\sum_{i=1}^m\varphi(\frac{w}{\gcd(w,i)})\cdot\varphi(i\cdot\gcd(w,i)) y⋅∑i=1mφ(gcd(w,i)w)⋅φ(i⋅gcd(w,i))

由于 gcd ⁡ ( w , i ) \gcd(w,i) gcd(w,i) 有的因子 i i i 也有,所以可以考虑将 g c d ( w , i ) gcd(w,i) gcd(w,i) 提取出来

= = = y ⋅ ∑ i = 1 m φ ( w gcd ⁡ ( w , i ) ) ⋅ φ ( i ) ⋅ gcd ⁡ ( w , i ) y\cdot\sum_{i=1}^m\varphi(\frac{w}{\gcd(w,i)})\cdot\varphi(i)\cdot\gcd(w,i) y⋅∑i=1mφ(gcd(w,i)w)⋅φ(i)⋅gcd(w,i)

此时考虑利用欧拉函数的性质 ∑ d ∣ n φ ( d ) = n \sum_{d|n}\varphi(d)=n ∑d∣nφ(d)=n 将 g c d ( w , i ) gcd(w,i) gcd(w,i) 转化成 φ ( ) \varphi() φ() 的形式

= = = y ⋅ ∑ i = 1 m φ ( w gcd ⁡ ( w , i ) ) ⋅ φ ( i ) ⋅ ∑ k ∣ gcd ⁡ ( w , i ) φ ( k ) y\cdot\sum_{i=1}^m\varphi(\frac{w}{\gcd(w,i)})\cdot\varphi(i)\cdot\sum_{k|\gcd(w,i)}\varphi(k) y⋅∑i=1mφ(gcd(w,i)w)⋅φ(i)⋅∑k∣gcd(w,i)φ(k)

此时观察发现 φ ( w gcd ⁡ ( w , i ) ) \varphi(\frac{w}{\gcd(w,i)}) φ(gcd(w,i)w) 和 φ ( k ) \varphi(k) φ(k) 之间有一定关系,所以可以再次转化:

= = = y ⋅ ∑ i = 1 m φ ( i ) ⋅ ∑ k ∣ gcd ⁡ ( w , i ) φ ( w k ) y\cdot\sum_{i=1}^m\varphi(i)\cdot\sum_{k|\gcd(w,i)}\varphi(\frac{w}{k}) y⋅∑i=1mφ(i)⋅∑k∣gcd(w,i)φ(kw)

= = = y ⋅ ∑ i = 1 m φ ( i ) ⋅ ∑ k ∣ w , k ∣ i φ ( w k ) y\cdot\sum_{i=1}^m\varphi(i)\cdot\sum_{k|w,k|i}\varphi(\frac{w}{k}) y⋅∑i=1mφ(i)⋅∑k∣w,k∣iφ(kw)

此时可以考虑更换枚举项的位置,把 k k k 的位置提前,同时:

= = = y ⋅ ∑ k ∣ w φ ( w k ) ⋅ ∑ i = 1 m k φ ( k ⋅ i ) y\cdot\sum_{k|w}\varphi(\frac{w}{k})\cdot\sum_{i=1}^{\frac{m}{k}}\varphi(k\cdot{i}) y⋅∑k∣wφ(kw)⋅∑i=1kmφ(k⋅i)

= = = y ⋅ ∑ k ∣ w φ ( w k ) ⋅ S ( k , m k ) y\cdot\sum_{k|w}\varphi(\frac{w}{k})\cdot{S(k,\frac{m}{k})} y⋅∑k∣wφ(kw)⋅S(k,km)

此时发现后面一部分是一个递归的形式,且当 n = 1 n=1 n=1 时 S ( n , m ) = ∑ i = 1 m φ ( i ) S(n,m) = \sum_{i=1}^m\varphi(i) S(n,m)=∑i=1mφ(i) 可以杜教筛算出来.

因此记忆化后即可解决该题.

— B Z O J 3512 BZOJ3512 BZOJ3512

莫比乌斯函数相关题目

题意:

求 ∑ i = 1 m μ ( n ⋅ i ) \sum_{i=1}^m\mu(n\cdot{i}) ∑i=1mμ(n⋅i) , n ≤ 1 0 12 n\le{10^{12}} n≤1012 , m ≤ 2 ⋅ 1 0 9 m\le{2\cdot10^9} m≤2⋅109

题解:

设 S ( n , m ) = ∑ i = 1 m μ ( n ⋅ i ) S(n,m)=\sum_{i=1}^m\mu(n\cdot{i}) S(n,m)=∑i=1mμ(n⋅i) .

则 ans = μ ( n ) ⋅ ∑ i = 1 m μ ( i ) ⋅ [ gcd ⁡ ( n , i ) = = 1 ] \mu(n)\cdot\sum_{i=1}^m\mu(i)\cdot[\gcd(n,i)==1] μ(n)⋅∑i=1mμ(i)⋅[gcd(n,i)==1]

= μ ( n ) ⋅ ∑ i = 1 m μ ( i ) ⋅ ∑ k ∣ gcd ⁡ ( n , i ) μ ( k ) \mu(n)\cdot\sum_{i=1}^m\mu(i)\cdot\sum_{k|\gcd(n,i)}\mu(k) μ(n)⋅∑i=1mμ(i)⋅∑k∣gcd(n,i)μ(k)

= μ ( n ) ⋅ ∑ k ∣ n μ ( k ) ⋅ ∑ i = 1 m k μ ( k ⋅ i ) \mu(n)\cdot\sum_{k|n}\mu(k)\cdot\sum_{i=1}^{\frac{m}{k}}\mu(k\cdot{i}) μ(n)⋅∑k∣nμ(k)⋅∑i=1kmμ(k⋅i)

= μ ( n ) ⋅ ∑ k ∣ n μ ( k ) ⋅ S ( k , m k ) \mu(n)\cdot\sum_{k|n}\mu(k)\cdot{S(k,\frac{m}{k})} μ(n)⋅∑k∣nμ(k)⋅S(k,km)

发现化简得到一个递归的形式,当 n = = 1 n==1 n==1 时为出口,用杜教筛求出 ∑ i = 1 m μ ( i ) \sum_{i=1}^m\mu(i) ∑i=1mμ(i) 即可.

小技巧: 只在最外面分解一次 n n n 的质因子,然后在求 S ( n , m ) S(n,m) S(n,m) 时,对于一个 n n n ,暴力判断哪些原始 n n n 的质因子可以整除现在的 $n $ ,然后二进制枚举 k k k 即可.

— 18 18 18 年徐州网络赛 e a s y m a t h easy math easymath

反演的巧妙应用

题意:

给定长度为n的数组a, 求 ∑ i = 1 n ∑ j = 1 n gcd ⁡ ( a [ i ] , a [ j ] ) ⋅ ( gcd ⁡ ( a [ i ] , a [ j ] ) − 1 ) \sum_{i=1}^n\sum_{j=1}^n\gcd(a[i],a[j])\cdot(\gcd(a[i],a[j])-1) ∑i=1n∑j=1ngcd(a[i],a[j])⋅(gcd(a[i],a[j])−1) .

1 ≤ n ≤ 1 0 4 1\le{n}\le10^4 1≤n≤104, 1 ≤ a [ i ] ≤ 1 0 4 1\le{a[i]}\le10^4 1≤a[i]≤104.

题解:

考虑直接枚举 gcd ⁡ ( a [ i ] , a [ j ] ) = = d \gcd(a[i],a[j])==d gcd(a[i],a[j])==d的对数统计. 用max表示a[i]的最大值.

用f(d) 表示 gcd ⁡ ( a [ i ] , a [ j ] ) = = d \gcd(a[i],a[j])==d gcd(a[i],a[j])==d 的对数, 用F(d)表示 d ∣ gcd ⁡ ( a [ i ] , a [ j ] ) d|\gcd(a[i],a[j]) d∣gcd(a[i],a[j]) 的对数.

F(d)可以较为轻松的预处理出来.

容易得到式子: ans = ∑ d = 1 m a x ( d 2 − d ) ⋅ f ( d ) \sum_{d=1}^{max}(d^2-d)\cdot{f(d)} ∑d=1max(d2−d)⋅f(d)

= ∑ d = 1 m a x ( d 2 − d ) ⋅ ∑ d ∣ x μ ( x d ) ⋅ F ( x ) \sum_{d=1}^{max}(d^2-d)\cdot\sum_{d|x}\mu(\frac{x}{d})\cdot{F(x)} ∑d=1max(d2−d)⋅∑d∣xμ(dx)⋅F(x)

由于此题式子化简后系数是 d 2 − d d^2-d d2−d ,且范围在 1 0 4 10^4 104,所以可以直接预处理后面一部分来计算.

当计算的是 g c d ( a [ i ] , a [ j ] ) gcd(a[i],a[j]) gcd(a[i],a[j])时,还可以继续化简.

— h d u 5212 hdu 5212 hdu5212

题意:

求: ∏ i = 1 n ∏ j = 1 m f i b [ gcd ⁡ ( i , j ) ] \prod_{i=1}^n\prod_{j=1}^mfib[\gcd(i,j)] ∏i=1n∏j=1mfib[gcd(i,j)] n , m ≤ 1 0 6 n,m\le{10^6} n,m≤106

题解:

根据反演基本套路,可得: ans = ∏ d = 1 m i n ( n , m ) f i b [ d ] f ( d ) \prod_{d=1}^{min(n,m)}fib[d]^{f(d)} ∏d=1min(n,m)fib[d]f(d)

ans = ∏ d = 1 m i n ( n , m ) f i b [ d ] ∑ d ∣ k μ ( k d ) ⋅ F ( k ) \prod_{d=1}^{min(n,m)}fib[d]^{\sum_{d|k}}\mu(\frac{k}{d})\cdot{F(k)} ∏d=1min(n,m)fib[d]∑d∣kμ(dk)⋅F(k)

ans = ∏ k = 1 m i n ( n , m ) ∏ d ∣ k f i b [ d ] μ ( k d ) ⋅ F ( k ) \prod_{k=1}^{min(n,m)}\prod_{d|k}fib[d]^{\mu(\frac{k}{d})\cdot{F(k)}} ∏k=1min(n,m)∏d∣kfib[d]μ(dk)⋅F(k)

ans = ∏ k = 1 m i n ( n , m ) ( ∏ d ∣ k f i b [ d ] μ ( k d ) ) F ( k ) \prod_{k=1}^{min(n,m)}(\prod_{d|k}fib[d]^{\mu(\frac{k}{d})})^{F(k)} ∏k=1min(n,m)(∏d∣kfib[d]μ(dk))F(k)

此时可以发现 ∏ d ∣ k f i b [ d ] μ ( k d ) \prod_{d|k}fib[d]^{\mu(\frac{k}{d})} ∏d∣kfib[d]μ(dk) 这一部分可以预处理,然后做一个前缀积,求次逆元,就可以和 F ( k ) F(k) F(k) 一起分块处理了.

— B Z O J 4816 BZOJ4816 BZOJ4816

题意:

有一个长为 l l l 的数组 a a a ,初始全是 0 0 0 ,现在有 q q q 个操作,第一种是 1 1 1 n n n d d d v v v ,表示给下标 x x x 满足 gcd ⁡ ( x , n ) = d \gcd(x,n)=d gcd(x,n)=d 的 a x a_x ax 增加 v v v ,第二种是 2 2 2 x x x ,查询 ∑ i = 1 x a i \sum_{i=1}^xa_i ∑i=1xai . 1 ≤ n , d , v ≤ 2 ⋅ 1 0 5 1\le{n,d,v}\le{2\cdot{10^5}} 1≤n,d,v≤2⋅105 .

题解:

首先列出第一种操作的式子: a x + = v ⋅ [ gcd ⁡ ( x , n ) = = d ] a_x += v \cdot [\gcd(x,n)==d] ax+=v⋅[gcd(x,n)==d]

尝试化简: v ⋅ [ gcd ⁡ ( x , n ) = = d ] v\cdot[\gcd(x,n)==d] v⋅[gcd(x,n)==d] = v ⋅ [ gcd ⁡ ( x d , n d ) = = 1 ] v\cdot[\gcd(\frac{x}{d},\frac{n}{d})==1] v⋅[gcd(dx,dn)==1] = v ⋅ ∑ k ∣ x d , k ∣ n d μ ( k ) v\cdot \sum_{k|\frac{x}{d},k|\frac{n}{d}} \mu(k) v⋅∑k∣dx,k∣dnμ(k)

此时观察可以发现,对于 k ∣ n d k|\frac{n}{d} k∣dn ,能贡献的 x x x 一定是 k ⋅ d k\cdot{d} k⋅d 的倍数.但是我们又不好直接去计算每一个 x x x .

因此考虑构造一个函数 f ( d ) f(d) f(d) : a x = ∑ d ∣ x f ( d ) a_x=\sum_{d|x}f(d) ax=∑d∣xf(d) . 此时对于每一个给定的 n , d n,d n,d ,我们只需要把对应的 k ⋅ d k\cdot{d} k⋅d 给加上 v ⋅ μ ( k ) v\cdot\mu(k) v⋅μ(k) 即可. 此时第二种操作的式子可以表示为: ∑ i = 1 x a i = ∑ i = 1 x ∑ d ∣ i f ( d ) = ∑ d = 1 x f ( d ) ⋅ ( x d ) \sum_{i=1}^xa_i = \sum_{i=1}^x\sum_{d|i}f(d) = \sum_{d=1}^xf(d)\cdot(\frac{x}{d}) ∑i=1xai=∑i=1x∑d∣if(d)=∑d=1xf(d)⋅(dx) ,可以分块做.

体会:

如果一个题中,每次会更新一个值的倍数,我们可以通过反演构造来转化问题.

— h d u 4947 hdu 4947 hdu4947

综合应用

题意:

求 : ∑ i = 1 A ∑ j = 1 B ∑ k = 1 C φ ( gcd ⁡ ( i , j 2 , k 3 ) ) \sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^C\varphi(\gcd(i,j^2,k^3)) ∑i=1A∑j=1B∑k=1Cφ(gcd(i,j2,k3)) A , B , C ≤ 1 0 7 A,B,C\le{10^7} A,B,C≤107

题解:

设 f ( d ) = ∑ i = 1 A ∑ j = 1 B ∑ k = 1 C [ gcd ⁡ ( i , j 2 , k 3 ) = = d ] f(d)=\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^C[\gcd(i,j^2,k^3)==d] f(d)=∑i=1A∑j=1B∑k=1C[gcd(i,j2,k3)==d]

F ( d ) = ∑ i = 1 A ∑ j = 1 B ∑ k = 1 C d ∣ gcd ⁡ ( i , j 2 , k 3 ) F(d)=\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^Cd|\gcd(i,j^2,k^3) F(d)=∑i=1A∑j=1B∑k=1Cd∣gcd(i,j2,k3)

令 ans = ∑ d = 1 m i n ( A , B 2 , C 3 ) φ ( d ) ⋅ f ( d ) \sum_{d=1}^{min(A,B^2,C^3)}\varphi(d)\cdot{f(d)} ∑d=1min(A,B2,C3)φ(d)⋅f(d)

ans = ∑ d = 1 m i n ( A , B 2 , C 3 ) φ ( d ) ⋅ ∑ d ∣ k μ ( k d ) ⋅ F ( k ) \sum_{d=1}^{min(A,B^2,C^3)}\varphi(d)\cdot{\sum_{d|k}\mu(\frac{k}{d})\cdot{F(k)}} ∑d=1min(A,B2,C3)φ(d)⋅∑d∣kμ(dk)⋅F(k)

ans = ∑ k = 1 m i n ( A , B 2 , C 3 ) F ( k ) ⋅ ∑ d ∣ k φ ( d ) ⋅ μ ( k d ) \sum_{k=1}^{min(A,B^2,C^3)}F(k)\cdot\sum_{d|k}\varphi(d)\cdot{\mu(\frac{k}{d})} ∑k=1min(A,B2,C3)F(k)⋅∑d∣kφ(d)⋅μ(dk)

可以发现,后面一部分是积性函数,可以线性筛出来.所以现在问题转化为求 F ( k ) F(k) F(k) .

容易发现 F ( d ) = ⌊ A f 1 ( d ) ⌋ ⌊ B f 2 ( d ) ⌋ ⌊ C f 3 ( d ) ⌋ F(d)= \lfloor\frac{A}{f_1(d)}\rfloor\lfloor\frac{B}{f_2(d)}\rfloor\lfloor\frac{C}{f_3(d)}\rfloor F(d)=⌊f1(d)A⌋⌊f2(d)B⌋⌊f3(d)C⌋ (由于 F ( d ) F(d) F(d) 有上下,所以外层枚举 k k k 的时候应取 m i n ( A , B , C ) min(A,B,C) min(A,B,C).)

当 x ∣ i k , x = ∏ p i q i x|i^k,x=\prod{p_i}^{q_i} x∣ik,x=∏piqi ,令 f k ( x ) = ∏ p i ⌈ q i k ⌉ f_k(x)=\prod{p_i^{\lceil\frac{qi}{k}\rceil}} fk(x)=∏pi⌈kqi⌉

可以发现 f k ( x ) f_k(x) fk(x) 也是积性函数,可以线性筛出来.因此该题得到解决.

— h d u 6428 hdu 6428 hdu6428

题意:

给定一个包含n个正整数的集合,有两种计算集合权值的办法:

计算集合的所有排列的所有区间的gcd之和.
对于从集合中选出k个数( k ∈ [ 1 , n ] {k}\in[1,n] k∈[1,n] )的所有方案,选出的数的gcd⋅k之和.

分别计算两种方式的权值并取模, 1 ≤ n ≤ 1 0 5 {1}\le{n}\le{10^5} 1≤n≤105,元素num范围 1 ≤ n u m ≤ 1 0 5 {1}\le{num}\le{10^5} 1≤num≤105.

题解:

用cnt[i]代表集合中是i及i的倍数的数的个数. max表示集合中最大的元素.

f(k,x)表示从集合中选取k个元素且这k个元素的gcd为x的种数.

F(k,x)表示从集合中选取k个元素且这k个元素的gcd为x或x的倍数的种数.

显而易见: F(k,x) = C c n t [ x ] k C_{cnt[x]}^k Ccnt[x]k.

第一种情况下的权值:

ans = ∑ k = 1 n ∑ x = 1 m a x f ( k , x ) ⋅ k ! ⋅ ( n − k + 1 ) ! ⋅ x \sum_{k=1}^n\sum_{x=1}^{max}f(k,x)\cdot{k!}\cdot{(n-k+1)!}\cdot{x} ∑k=1n∑x=1maxf(k,x)⋅k!⋅(n−k+1)!⋅x

= ∑ k = 1 n k ! ⋅ ( n − k + 1 ) ! ⋅ ∑ x = 1 m a x x ⋅ ∑ x ∣ d μ ( d x ) ⋅ F ( k , d ) \sum_{k=1}^nk!\cdot(n-k+1)!\cdot\sum_{x=1}^{max}x\cdot\sum_{x|d}\mu(\frac{d}{x})\cdot{F(k,d)} ∑k=1nk!⋅(n−k+1)!⋅∑x=1maxx⋅∑x∣dμ(xd)⋅F(k,d) (反演常用套路.)

= ∑ k = 1 n k ! ⋅ ( n − k + 1 ) ! ⋅ ∑ d = 1 m a x F ( k , d ) ⋅ ∑ x ∣ d μ ( d x ) ⋅ x \sum_{k=1}^nk!\cdot(n-k+1)!\cdot\sum_{d=1}^{max}F(k,d)\cdot\sum_{x|d}\mu(\frac{d}{x})\cdot{x} ∑k=1nk!⋅(n−k+1)!⋅∑d=1maxF(k,d)⋅∑x∣dμ(xd)⋅x (更换枚举项)

= ∑ k = 1 n k ! ⋅ ( n − k + 1 ) ! ⋅ ∑ d = 1 m a x F ( k , d ) ⋅ φ ( d ) \sum_{k=1}^nk!\cdot(n-k+1)!\cdot\sum_{d=1}^{max}F(k,d)\cdot\varphi(d) ∑k=1nk!⋅(n−k+1)!⋅∑d=1maxF(k,d)⋅φ(d)

= ∑ d = 1 m a x φ ( d ) ⋅ ∑ k = 1 n k ! ⋅ ( n − k + 1 ) ⋅ F ( k , d ) \sum_{d=1}^{max}\varphi(d)\cdot\sum_{k=1}^nk!\cdot(n-k+1)\cdot{F(k,d)} ∑d=1maxφ(d)⋅∑k=1nk!⋅(n−k+1)⋅F(k,d) (前后调换位置)

= ∑ d = 1 m a x φ ( d ) ⋅ c n t [ d ] ! ⋅ ∑ k = 1 c n t [ d ] ( n − k + 1 ) ! ( c n t [ d ] − k ) ! \sum_{d=1}^{max}\varphi(d)\cdot{cnt[d]!}\cdot\sum_{k=1}^{cnt[d]}\frac{(n-k+1)!}{(cnt[d]-k)!} ∑d=1maxφ(d)⋅cnt[d]!⋅∑k=1cnt[d](cnt[d]−k)!(n−k+1)! (可有F(k,d)的公式展开后化简得)

由手动推导或者公式: ∑ k = 1 x ( n − k + 1 ) ! ( x − k ) ! = ( n + 1 ) ! ( x − 1 ) ! ⋅ ( n − x + 2 ) \sum_{k=1}^x\frac{(n-k+1)!}{(x-k)!} = \frac{(n+1)!}{(x-1)!\cdot(n-x+2)} ∑k=1x(x−k)!(n−k+1)!=(x−1)!⋅(n−x+2)(n+1)! 可将原式再次化简:

= ∑ d = 1 m a x φ ( d ) ⋅ c n t [ d ] ! ⋅ ( n + 1 ) ! ( c n t [ d ] − 1 ) ! ⋅ ( n − c n t [ d ] + 2 ) \sum_{d=1}^{max}\varphi(d)\cdot{cnt[d]!}\cdot\frac{(n+1)!}{(cnt[d]-1)!\cdot(n-cnt[d]+2)} ∑d=1maxφ(d)⋅cnt[d]!⋅(cnt[d]−1)!⋅(n−cnt[d]+2)(n+1)!

第二种情况下的权值:

ans = ∑ k = 1 n ∑ x = 1 m a x f ( k , x ) ⋅ k ⋅ x \sum_{k=1}^n\sum_{x=1}^{max}f(k,x)\cdot{k}\cdot{x} ∑k=1n∑x=1maxf(k,x)⋅k⋅x

= ∑ k = 1 n k ⋅ ∑ d = 1 m a x φ ( d ) ⋅ F ( k , d ) \sum_{k=1}^nk\cdot\sum_{d=1}^{max}\varphi(d)\cdot{F(k,d)} ∑k=1nk⋅∑d=1maxφ(d)⋅F(k,d) (化简过程同上)

= ∑ d = 1 m a x φ ( d ) ⋅ ∑ k = 1 c n t [ d ] k ⋅ C c n t [ d ] k \sum_{d=1}^{max}\varphi(d)\cdot\sum_{k=1}^{cnt[d]}k\cdot{C_{cnt[d]}^k} ∑d=1maxφ(d)⋅∑k=1cnt[d]k⋅Ccnt[d]k (k的范围根据其上限调整了)

= ∑ d = 1 m a x φ ( d ) ⋅ c n t [ d ] ⋅ ∑ k = 1 c n t [ d ] C c n t [ d ] − 1 k \sum_{d=1}^{max}\varphi(d)\cdot{cnt[d]}\cdot\sum_{k=1}^{cnt[d]}C_{cnt[d]-1}^k ∑d=1maxφ(d)⋅cnt[d]⋅∑k=1cnt[d]Ccnt[d]−1k (将k带入组合数里面然后化简一下)

= ∑ d = 1 m a x φ ( d ) ⋅ c n t [ d ] ⋅ 2 c n t [ d ] − 1 \sum_{d=1}^{max}\varphi(d)\cdot{cnt[d]}\cdot{2^{cnt[d]-1}} ∑d=1maxφ(d)⋅cnt[d]⋅2cnt[d]−1 (再次化简)

体会:

给定集合选数gcd的题一定要先列出式子,然后再一步一步化简.

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
const int mod = 258280327;
long long fac[maxn*2+5],inv[maxn*2+5];//预处理阶乘和阶乘的逆元.
int prime[maxn+5],phi[maxn+5],vis[maxn+5],cnt[maxn+5];//vis记录每个数字出现了多少次t记录每个数字的倍数出现了多少次.
long long pow_2[maxn+5];
long long qpow(long long x,long long y)
{long long res=1;while(y){if(y&1) res=(res*x)%mod;x=(x*x)%mod;y>>=1;}return res;
}
void init()
{phi[1]=1;fac[0]=1;pow_2[0]=1;for(int i=2;i<=maxn;i++){if(!prime[i]) prime[++prime[0]]=i,phi[i]=i-1;for(int j=1;j<=prime[0]&&prime[j]<=maxn/i;j++){prime[i*prime[j]]=1;if(i%prime[j]==0) {phi[i*prime[j]]=phi[i]*prime[j];break;}else phi[i*prime[j]]=phi[i]*phi[prime[j]];}}for(int i=1;i<=2*maxn;i++) fac[i]=fac[i-1]*i%mod;inv[2*maxn]=qpow(fac[2*maxn],mod-2);for(int i=2*maxn-1;i>=0;i--) inv[i]=(1LL*inv[i+1]*(i+1))%mod;for(int i=1;i<=maxn;i++) pow_2[i]=1LL*pow_2[i-1]*2%mod;
}
long long C(int n,int m){if(n<0||m>n) return 0;return fac[n]*inv[m]%mod*inv[n-m]%mod;}
int main()
{int n,x,mx;init();while(~scanf("%d",&n)){memset(vis,0,sizeof(vis));memset(cnt,0,sizeof(cnt));mx=0;for(int i=1;i<=n;i++) scanf("%d",&x),vis[x]++,mx=max(mx,x);for(int i=1;i<=mx;i++)//与数组和gcd相关的题大部分都要做这一步.for(int j=i;j<=mx;j+=i)cnt[i]+=vis[j];//记录为i的倍数的数有多少个.long long ans1=0,ans2=0;for(int i=1;i<=mx;i++){if(!cnt[i]) continue;ans1=(ans1+1LL*phi[i]*fac[cnt[i]]%mod*fac[n-cnt[i]+1]%mod*C(n+1,cnt[i]-1)%mod)%mod;ans2=(ans2+1LL*cnt[i]*pow_2[cnt[i]-1]%mod*phi[i]%mod)%mod;}if(ans1>ans2) printf("Mr. Zstu ");else if(ans1==ans2) printf("Equal ");else printf("Mr. Hdu ");printf("%lld\n",max(ans1,ans2));}return 0;
}

— h d u 5321 hdu5321 hdu5321

题意:

定义 r a d ( n ) rad(n) rad(n) 表示 n n n 的因子中最大的无平方因子数. f ( n ) = r a d ( n ) ⋅ φ ( n r a d ( n ) ) f(n) = rad(n)\cdot\varphi(\frac{n}{rad(n)}) f(n)=rad(n)⋅φ(rad(n)n)

g ( n ) = ∑ d ∣ n f ( d ) g(n)=\sum_{d|n}f(d) g(n)=∑d∣nf(d) , 求 ∑ i = 1 n g ( i ) \sum_{i=1}^ng(i) ∑i=1ng(i) , 其中 n ≤ 1 0 12 n\le{10^{12}} n≤1012 .

题解:

首先,我们只考虑如何化简求 g ( n ) g(n) g(n) , 观察发现,对于 f ( n ) f(n) f(n) 这个函数来说,貌似没办法直接化简,因此,我们可以尝试拆分 n n n 为素因子,对每一个素因子考虑贡献来计算答案,此时式子可以表示为 :

g ( n ) = ∏ i = 1 t ∑ j = 0 q i f ( p i j ) g(n) = \prod_{i=1}^{t}\sum_{j=0}^{q_i}f({p_i}^j) g(n)=∏i=1t∑j=0qif(pij)

= = = ∏ i = 1 t ( 1 + ∑ j = 1 q i f ( p i j ) ) \prod_{i=1}^t(1+\sum_{j=1}^{q_i}f({p_i}^j)) ∏i=1t(1+∑j=1qif(pij))

= = = ∏ i = 1 t ( 1 + ∑ j = 1 q i ( p i ⋅ φ ( p i j − 1 ) ) ) \prod_{i=1}^t(1+\sum_{j=1}^{q_i}(p_i\cdot\varphi(p_i^{j-1}))) ∏i=1t(1+∑j=1qi(pi⋅φ(pij−1)))

= = = ∏ i = 1 t ( 1 + p i q i ) \prod_{i=1}^t(1+p_i^{q_i}) ∏i=1t(1+piqi)

由 g ( n ) g(n) g(n) 的式子化简可以发现,对于 g ( n ) g(n) g(n) 有贡献的值要么不取某一个素因子,要么取完某一个素因子.

所以: g ( n ) g(n) g(n) = = = ∑ d ∣ n d ⋅ [ gcd ⁡ ( d , n d ) = = 1 ] \sum_{d|n}d\cdot[\gcd(d,\frac{n}{d})==1] ∑d∣nd⋅[gcd(d,dn)==1]

= = = ∑ i = 1 n ∑ j = 1 n i ⋅ [ gcd ⁡ ( i , j ) = = 1 ] ⋅ [ i ⋅ j = = n ] \sum_{i=1}^n\sum_{j=1}^ni\cdot[\gcd(i,j)==1]\cdot[i\cdot{j}==n] ∑i=1n∑j=1ni⋅[gcd(i,j)==1]⋅[i⋅j==n]

此时发现: ∑ i = 1 n g ( i ) = ∑ i = 1 n ∑ j = 1 n i ⋅ [ gcd ⁡ ( i , j ) = = 1 ] ⋅ [ i ⋅ j ≤ n ] \sum_{i=1}^ng(i)=\sum_{i=1}^n\sum_{j=1}^ni\cdot[\gcd(i,j)==1]\cdot[i\cdot{j}\le{n}] ∑i=1ng(i)=∑i=1n∑j=1ni⋅[gcd(i,j)==1]⋅[i⋅j≤n]

= = = ∑ i = 1 n ∑ j = 1 n ∑ k ∣ gcd ⁡ ( i , j ) μ ( k ) ⋅ i ⋅ [ i ⋅ j ≤ n ] \sum_{i=1}^n\sum_{j=1}^n\sum_{k|\gcd(i,j)}\mu(k)\cdot{i}\cdot[i\cdot{j}\le{n}] ∑i=1n∑j=1n∑k∣gcd(i,j)μ(k)⋅i⋅[i⋅j≤n]

= = = ∑ k = 1 n k ⋅ μ ( k ) ⋅ ∑ i = 1 n k i ⋅ ∑ j = 1 n k [ i ⋅ j ⋅ k 2 ≤ n ] \sum_{k=1}^nk\cdot\mu(k)\cdot\sum_{i=1}^{\frac{n}{k}}i\cdot\sum_{j=1}^{\frac{n}{k}}[i\cdot{j}\cdot{k^2}\le{n}] ∑k=1nk⋅μ(k)⋅∑i=1kni⋅∑j=1kn[i⋅j⋅k2≤n]

容易发现将前面的枚举规定严格后,后面的部分就可以直接去掉.

= = = ∑ k = 1 n k ⋅ μ ( k ) ⋅ ∑ i = 1 n k 2 i ⋅ ⌊ n k 2 ⋅ i ⌋ \sum_{k=1}^{\sqrt{n}}k\cdot\mu(k)\cdot\sum_{i=1}^{\frac{n}{k^2}}i\cdot\lfloor\frac{n}{k^2\cdot{i}}\rfloor ∑k=1n k⋅μ(k)⋅∑i=1k2ni⋅⌊k2⋅in⌋

注意到最后一部分是 ∑ i = 1 n i ⋅ ⌊ n i ⌋ \sum_{i=1}^ni\cdot\lfloor\frac{n}{i}\rfloor ∑i=1ni⋅⌊in⌋ 的形式,即为 ∑ i = 1 n σ ( i ) \sum_{i=1}^n\sigma(i) ∑i=1nσ(i) ,因此最后式子化为:

= = = ∑ k = 1 n k ⋅ μ ( k ) ⋅ ∑ i = 1 n k 2 σ ( i ) \sum_{k=1}^{\sqrt{n}}k\cdot\mu(k)\cdot\sum_{i=1}^{\frac{n}{k^2}}\sigma(i) ∑k=1n k⋅μ(k)⋅∑i=1k2nσ(i)

— Z O J 3881 ZOJ3881 ZOJ3881

min_25筛

概念

问题:

对于积性函数 f ( x ) f(x) f(x) ,求 ∑ i = 1 n f ( i ) , n ≤ 1 0 10 \sum_{i=1}^nf(i),n\le{10^{10}} ∑i=1nf(i),n≤1010

要求:

f ( x ) f(x) f(x) 满足 f ( p ) f(p) f(p) 可以用多项式表示,且可以快速求出 f ( p k ) f(p^k) f(pk) .(p指质数)

预处理:

设 P P P 为质数集合, P i P_i Pi 表示第 i i i 个质数.

先不考虑怎么求答案,考虑求这个式子: ∑ i = 2 n f ( i ) ⋅ [ i ∈ P ] \sum_{i=2}^nf(i)\cdot[i\in{P}] ∑i=2nf(i)⋅[i∈P]

设 g ( n , j ) = ∑ i = 2 n f ( i ) ⋅ [ i ∈ P g(n,j) = \sum_{i=2}^nf(i)\cdot[i\in{P} g(n,j)=∑i=2nf(i)⋅[i∈P 或 i i i 的最小质因子大于 P j ] P_j] Pj]

考虑 g ( n , j ) g(n,j) g(n,j) 的转移方程.

当 P j 2 > n P_j^2>n Pj2>n 时, P j P_j Pj 不会产生贡献,有 g ( n , j ) = g ( n , j − 1 ) g(n,j)=g(n,j-1) g(n,j)=g(n,j−1)

当 P j 2 ≤ n P_j^2\le{n} Pj2≤n 时, 要减去最小质因子为 P j P_j Pj 的贡献,即减去 f ( P j ) ⋅ ( g ( n P j , j − 1 ) − g ( P j − 1 , j − 1 ) ) f(P_j)\cdot(g(\frac{n}{P_j},j-1)-g(P_j-1,j-1)) f(Pj)⋅(g(Pjn,j−1)−g(Pj−1,j−1))

显然可以知道: 我们要求的 ∑ i = 1 n f ( i ) ⋅ [ i ∈ P ] = g ( n , ∣ P ∣ ) \sum_{i=1}^nf(i)\cdot[i\in{P}]=g(n,|P|) ∑i=1nf(i)⋅[i∈P]=g(n,∣P∣) ,由于无法直接求 g ( n , j ) g(n,j) g(n,j) ,所以初始把所有的数都当作质数来求 g ( n , j ) g(n,j) g(n,j) ,然后只取其中的质数,即可得到答案.因此在非递归写法中,初始化每一个 g g g 数组为把 2 2 2 ~ i i i 中每一个数都当作质数的情况下的值,(假设 f ( p ) = p k f(p)=p^k f(p)=pk ,那么 g ( n , 0 ) = ∑ i = 2 n i k g(n,0)=\sum_{i=2}^ni^k g(n,0)=∑i=2nik ) 然后再转移即可.注意 g ( P j − 1 , j − 1 ) g(P_j-1,j-1) g(Pj−1,j−1) 是可以直接求的,等于 ∑ i = 1 j − 1 f ( P i ) \sum_{i=1}^{j-1}f(P_i) ∑i=1j−1f(Pi)

计算答案:

当做完上一步之后,考虑求真正的前缀和.设: S ( n , j ) = ∑ i = 2 n f ( i ) ⋅ [ i ∈ P S(n,j)=\sum_{i=2}^nf(i)\cdot[i\in{P} S(n,j)=∑i=2nf(i)⋅[i∈P 或 i i i 的最小质因子大于等于 P j ] P_j] Pj]

此时要求的答案就是 S ( n , 1 ) S(n,1) S(n,1) .把 S ( n , j ) S(n,j) S(n,j) 分为质数,合数,1来分别计算,则:

S ( n , j ) = g ( n , ∣ P ∣ ) − ∑ i = 1 j − 1 f ( P i ) + ∑ k ≥ j ∑ e ( f ( P k e ) ⋅ S ( n P k e , k + 1 ) + f ( P k e + 1 ) ) S(n,j)=g(n,|P|)-\sum_{i=1}^{j-1}f(P_i)+\sum_{k\ge{j}}\sum_{e}(f(P_k^e)\cdot{S(\frac{n}{P_k^e},k+1)}+f(P_k^{e+1})) S(n,j)=g(n,∣P∣)−∑i=1j−1f(Pi)+∑k≥j∑e(f(Pke)⋅S(Pken,k+1)+f(Pke+1))

预处理 g g g 后,直接递归计算 S ( n , 1 ) S(n,1) S(n,1) 即可.

复杂度: O ( n 3 4 log ⁡ n ) O(\frac{n^\frac{3}{4}}{\log{n}}) O(lognn43)

题目

题意:

求 ∑ i = 1 n d ( i k ) \sum_{i=1}^nd(i^k) ∑i=1nd(ik) ( m o d (mod (mod 2 64 ) 2^{64} ) 264) n , k ≤ 1 0 10 n,k\le{10^{10}} n,k≤1010

题解:

考虑用min_25筛解决此题:

f ( 1 ) = 1 , f ( p ) = k + 1 , f ( p c ) = k ⋅ c + 1 f(1)=1 , f(p)=k+1 ,f(p^c)=k\cdot{c}+1 f(1)=1,f(p)=k+1,f(pc)=k⋅c+1 .

本来 g ( n , 0 ) = ∑ i = 2 n k + 1 g(n,0)=\sum_{i=2}^n{k+1} g(n,0)=∑i=2nk+1 ,考虑在计算的过程中先不乘以 k + 1 k+1 k+1 ,再最后计算 S S S 的时候再乘上去,所以初始化 g ( n , 0 ) = ∑ i = 2 n = n − 1 g(n,0)=\sum_{i=2}^n=n-1 g(n,0)=∑i=2n=n−1 . 即 g ( n , ∣ P ∣ ) ⋅ ( k + 1 ) = ∑ i = 2 n f ( i ) ⋅ [ i ∈ P ] g(n,|P|)\cdot(k+1)=\sum_{i=2}^nf(i)\cdot[i\in{P}] g(n,∣P∣)⋅(k+1)=∑i=2nf(i)⋅[i∈P]

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull maxn = 233333;//maxn代表的是分块的块数,设置为sqrt(n).
ull n,k,cntp,m,sn,id1[maxn+5],id2[maxn+5],w[maxn+5];
ull prime[maxn+5],g[maxn+5];
bool vis[maxn+5];
ull S(ull x,ull y)
{if(x<prime[y]||x<=1) return 0;ull id=(x<=sn)?id1[x]:id2[n/x];//找到x对应的块.ull res = g[id]*(k+1)-(y-1)*(k+1);//加上前一部分.for(ull i=y;i<=cntp&&prime[i]*prime[i]<=x;i++){ull t=prime[i],t2=prime[i]*prime[i];for(ull j=1;t2<=x;j++,t=t2,t2*=prime[i])res+=((k*j+1)*S(x/t,i+1)+(k*(j+1)+1));}return res;
}
void solve()
{scanf("%lld%lld",&n,&k); sn=sqrt(n);cntp=m=0;//cntp代表质数的数量,m代表块的数量.for(ull i=2;i<=sn;i++){if(!vis[i]){prime[++cntp]=i;}for(ull j=1;j<=cntp&&i*prime[j]<=sn;j++){vis[i*prime[j]]=1;if(i%prime[j]==0) break;}}//g数组预处理第一维所有可能取值,然后第二层转移.for(ull l=1,r;l<=n;l=r+1){r=n/(n/l);//分块得右边界w[++m]=n/l;//记录每一块的id和值.g[m]=(w[m]-1);//初始化的上界为w[m],同时还要减掉1.if(w[m]<=sn) id1[w[m]]=m;//给两种情况下的块分别取id.else id2[n/w[m]]=m;}for(ull i=1;i<=cntp;i++){//枚举每一个prime[i],考虑其能贡献的所有w[j],然后更新一层.for(ull j=1;j<=m&&prime[i]*prime[i]<=w[j];j++){ull d=w[j]/prime[i];ull id=(d<=sn)?id1[d]:id2[n/d];//id表示n/pj对应的块.g[j]-=(g[id]-i+1);//减去转移方程对应的部分.}}printf("%llu\n",S(n,1)+1);//1要特殊处理.
}
int main()
{int t;scanf("%d",&t);while(t--) solve();return 0;
}

— S P O J SPOJ SPOJ D I V C N T K DIVCNTK DIVCNTK

题意:

定义一个函数 f ( x ) f(x) f(x) , 满足:

1. f ( 1 ) = 1 f(1)=1 f(1)=1

2. f ( p c ) = p ⨁ c f(p^c)=p\bigoplus{c} f(pc)=p⨁c ( p p p 为质数, ⨁ \bigoplus ⨁ 表示异或)

3. f ( a ⋅ b ) = f ( a ) ⋅ f ( b ) f(a\cdot{b})=f(a)\cdot{f(b)} f(a⋅b)=f(a)⋅f(b) ( a a a 和 b b b 互质)

求 ∑ i = 1 n f ( i ) \sum_{i=1}^nf(i) ∑i=1nf(i) m o d ( 1 0 9 + 7 ) mod(10^9+7) mod(109+7)

题解:

考虑用 min_25 筛解决此题.

对应质数 p p p ,有 f ( p ) = p f(p)=p f(p)=p x o r xor xor 1 1 1 . 除了 f ( 2 ) = 3 f(2)=3 f(2)=3 , 其余 f ( p ) = p − 1 f(p)=p-1 f(p)=p−1 .

那么转化成积性函数 g ( x ) = x , h ( x ) = 1 g(x)=x,h(x)=1 g(x)=x,h(x)=1 ,求出 g ( n , ∣ P ∣ ) , h ( n , ∣ P ∣ ) g(n,|P|),h(n,|P|) g(n,∣P∣),h(n,∣P∣)

则 ∑ i = 1 n f ( i ) ⋅ [ i ∈ P ] = g ( n , ∣ P ∣ ) − h ( n , ∣ P ∣ ) \sum_{i=1}^nf(i)\cdot[i\in{P}]=g(n,|P|)-h(n,|P|) ∑i=1nf(i)⋅[i∈P]=g(n,∣P∣)−h(n,∣P∣) .注意遇到 f ( 2 ) f(2) f(2) 时要额外 + 2 +2 +2 .

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int maxn = 2e5+1e4+7;//maxn代表的是分块的块数,设置为sqrt(n).
const ll inv2 = 500000004;
int prime[maxn+5];
bool vis[maxn+5];
ll n,m,sn,cntp,id1[maxn+5],id2[maxn+5],w[maxn+5];
ll g[maxn+5],h[maxn+5],sump[maxn+5];
ll S(ll x,ll y)
{if(x<prime[y]||x<=1) return 0;ll id = (x<=sn)?id1[x]:id2[n/x];ll res = ((g[id]-h[id])-(sump[y-1]-(y-1)))%mod;if(y==1) res+=2;//有1的情况需要额外+2.for(ll i=y;i<=cntp&&prime[i]*prime[i]<=x;i++){ll t=prime[i],t2=prime[i]*prime[i];for(ll j=1;t2<=x;j++,t=t2,t2*=prime[i])res=(res+(prime[i]^j)*S(x/t,i+1)%mod+(prime[i]^(j+1))%mod)%mod;}return res;
}
int main()
{scanf("%lld",&n); sn=sqrt(n);cntp=m=0;//cntp代表质数的数量,m代表块的数量.for(ll i=2;i<=sn;i++){if(!vis[i]){prime[++cntp]=i;sump[cntp]=(sump[cntp-1]+i)%mod;//记录质数前缀和.}for(ll j=1;j<=cntp&&i*prime[j]<=maxn;j++){vis[i*prime[j]]=1;if(i%prime[j]==0) break;}}//g数组预处理第一维所有可能取值,然后第二层转移.for(ll l=1,r;l<=n;l=r+1){r=n/(n/l);//分块得右边界w[++m]=n/l;//记录每一块的id和值.g[m]=(w[m]%mod*((w[m]+1)%mod)%mod*inv2%mod+mod-1)%mod;//g[i]=i的和.h[m]=(w[m]-1)%mod;//h[i]=1的和.if(w[m]<=sn) id1[w[m]]=m;else id2[n/w[m]]=m;}for(ll i=1;i<=cntp;i++){for(ll j=1;j<=m&&prime[i]*prime[i]<=w[j];j++){ll d = w[j]/prime[i];ll id = (d<=sn)?id1[d]:id2[n/d];g[j]=((g[j]-prime[i]*(g[id]-sump[i-1])%mod)%mod+mod)%mod;h[j]=((h[j]-(h[id]-i+1))%mod+mod)%mod;//分别更新g[j],h[j].}}printf("%lld\n",(S(n,1)+mod+1+mod)%mod);return 0;
}

— L O J 6053 LOJ6053 LOJ6053

题意:

一个合数的真因数指不包含本身的因数,现在求 l l l ~ r r r 之间的合数的最大真因数之和. l , r ≤ 5 ⋅ 1 0 9 l,r\le{5\cdot10^9} l,r≤5⋅109

题解:

考虑在min_25筛中,初始化 g ( n , 0 ) = ∑ i = 2 n i g(n,0)=\sum_{i=2}^ni g(n,0)=∑i=2ni ,可以发现在转移方程中:

KaTeX parse error: Expected '}', got 'EOF' at end of input: …,j-1) & \text{P_j^2>nKaTeX parse error: Expected 'EOF', got '}' at position 1: }̲ \\ g(n,j-1)-f(…P_j^2\le{n}KaTeX parse error: Expected 'EOF', got '}' at position 1: }̲ \end{cases}

g ( n P j , j − 1 ) − g ( P j − 1 , j − 1 ) g(\frac{n}{P_j},j-1)-g(P_j-1,j-1) g(Pjn,j−1)−g(Pj−1,j−1) 对应的就是满足最小质因子是 P j P_j Pj 的情况下的和.因此直接统计这一部分即可.

注意: 此题是只求合数的.直接套用时需要注意.

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+7;
typedef long long ll;
ll sn,cntp,m,w[maxn+5],g[maxn+5],id1[maxn+5],id2[maxn+5];
ll prime[maxn+5],psum[maxn+5];
bool vis[maxn+5];
ll solve(ll n)
{if(n<=2) return 0; sn=sqrt(n);cntp=m=0;memset(vis,false,sizeof(vis));for(ll i=2;i<=sn;i++){if(!vis[i]) prime[++cntp]=i,psum[cntp]=psum[cntp-1]+i;for(int j=1;j<=cntp&&i*prime[j]<=sn;j++){vis[i*prime[j]]=1;if(i%prime[j]==0) break;}}for(ll l=1,r;l<=n;l=r+1){r=n/(n/l); w[++m]=n/l;g[m]=(w[m]+2)*(w[m]-1)/2;//与i*(i+1)/2-1等效.if(w[m]<=sn) id1[w[m]]=m;else id2[n/w[m]]=m;}ll ans=0;for(ll i=1;i<=cntp;i++){for(ll j=1;j<=m&&prime[i]*prime[i]<=w[j];j++){ll d=w[j]/prime[i];ll id=(d<=sn)?id1[d]:id2[n/d];g[j]-=prime[i]*(g[id]-psum[i-1]);if(j==1) ans+=g[id]-psum[i-1];//只有j=1的情况才对答案有贡献.}}return ans;
}
int main()
{ll l,r;while(~scanf("%lld%lld",&l,&r))printf("%lld\n",solve(r)-solve(l-1));return 0;
}

— 最大真因数 ( o j oj oj 挂掉了)

题意:

求 ∑ i = 1 N ∑ j = 1 N s g c d ( i , j ) k \sum_{i=1}^N\sum_{j=1}^Nsgcd(i,j)^k ∑i=1N∑j=1Nsgcd(i,j)k m o d mod mod 2 32 2^{32} 232.其中 s g c d ( i , j ) sgcd(i,j) sgcd(i,j) 表示 i , j i,j i,j 的公约数中第二大的,如果 gcd ⁡ ( i , j ) = = 1 \gcd(i,j)==1 gcd(i,j)==1 ,那么 s g c d ( i , j ) = 0 sgcd(i,j)=0 sgcd(i,j)=0 . N ≤ 1 0 9 , k ≤ 50 N\le{10^9},k\le50 N≤109,k≤50

题解:

考虑 f ( n ) = n m i n p ( n ) f(n)=\frac{n}{minp(n)} f(n)=minp(n)n . 反演一波将答案转化为 ∑ d = 2 n f ( d ) k ⋅ ( 2 ⋅ ∑ i = 1 n d φ ( i ) − 1 ) \sum_{d=2}^nf(d)^k\cdot(2\cdot\sum_{i=1}^{\frac{n}{d}}\varphi(i)-1) ∑d=2nf(d)k⋅(2⋅∑i=1dnφ(i)−1)

容易发现如果可以求出 f ( d ) k f(d)^k f(d)k 的前缀和,那么后面一部分杜教筛出来,即可分块处理得到答案.

考虑如何求 f ( d ) k f(d)^k f(d)k 的前缀和 ,可以发现 f ( d ) f(d) f(d) 等价于 d d d 的最大真因数(素数的部分单独讨论). 因此在求最大真因数的基础上加一个求自然数幂和即可解决问题.

#include<cmath>
#include<cstdio>
#define ll long long
#define ul unsigned int
#define fo(i, x, y) for(int i = x; i <= y; i ++)
using namespace std;
const int N = 1e6 + 5;
int n, k, sqr, m;
int bz[N]; ul p[N], phi[N];
int w[N], i1[N], i2[N];
ul s[51][51], g[N], sk[N], sp[N], sum[N], h[N], c[N];
ul ksm(ul x, ul y) {ul s = 1;for(; y; y /= 2, x = x * x)if(y & 1) s = s * x;return s;
}
void sieve(int n) {fo(i, 2, n) bz[i] = 0; p[0] = 0;fo(i, 2, n) {if(!bz[i]){//sk代表p^k,sp代表sk的前缀和.p[++ p[0]] = i; phi[i] = i - 1; sk[p[0]] = ksm(i, k);sp[p[0]] = sp[p[0] - 1] + sk[p[0]]; c[i] = sk[p[0]];}//c代表i^k.for(int j = 1; i * p[j] <= n; j ++) {int k = i * p[j]; bz[k] = 1;c[k] = c[i] * c[p[j]];if(i % p[j] == 0) { phi[k] = phi[i] * p[j]; break;}phi[k] = phi[i] * phi[p[j]];}}phi[1] = c[1] = 1;//做一次前缀和.fo(i, 2, n) phi[i] += phi[i - 1], c[i] += c[i - 1];
}
ul zm(int n) {//计算1~n的自然幂和.if(n <= 1e6) return c[n];ul S = 0;fo(j, 1, k) {ul p = 1;fo(i, n - j + 1, n + 1)p *= (i % (j + 1) == 0 ? i / (j + 1) : i);S += s[k][j] * p;}return S;
}
int bx[N]; ul bs[N];
ul dg(int x) {//杜教筛出phi的前缀和.if(x <= 1e6) return phi[x];int k = x <= sqr ? i1[x] : i2[n / x];if(bx[k]) return bs[k];bx[k] = 1; bs[k] = (ul) x * (x + 1) / 2;for(int i = 2, j; i <= x; i = j + 1) {j = x / (x / i);bs[k] -= dg(x / i) * (j - i + 1);}return bs[k];
}
ul ans;
int main() {scanf("%d %d", &n, &k); sqr = sqrt(n);sieve(N - 5);s[0][0] = 1; fo(i, 1, k) fo(j, 1, i) s[i][j] = s[i - 1][j - 1] + s[i - 1][j] * j;for(int i = 1, j; i <= n; i = j + 1) {j = n / (n / i); w[++ m] = n / i;if(w[m] <= sqr) i1[w[m]] = m; else i2[n / w[m]] = m;h[m] = w[m] - 1;//初始化质数的.g[m] = zm(w[m]) - 1;//初始化合数的.}p[0] = 0; while(p[p[0] + 1] <= sqr) p[0] ++;fo(j, 1, p[0]) for(int i = 1; i <= m && p[j] * p[j] <= w[i]; i ++) {int k = (w[i] / p[j] <= sqr) ? i1[w[i] / p[j]] : i2[n / (w[i] / p[j])];g[i] -= sk[j] * (g[k] - sp[j - 1]); h[i] -= h[k] - j + 1;sum[i] += g[k] - sp[j - 1];}fo(i, 1, m) sum[i] += h[i];//统计上质数的贡献.fo(i, 1, m) ans += (sum[i] - sum[i + 1]) * (dg(n / w[i]) * 2 - 1);printf("%u", ans);
}

— 51 N o d 1847 51Nod1847 51Nod1847

更多推荐

莫比乌斯反演总结

本文发布于:2024-03-09 09:58:59，感谢您对本站的认可！

本文链接:https://www.elefans.com/category/jswz/34/1724663.html