差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:数论_4 [2020/09/22 14:59]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:数论_4 [2020/09/23 09:11] (当前版本)
jxm2001 [算法例题]
@@ 行 9: / 行 9: @@
 ==== 算法思路 ====
-首先给定 $\text{Min_25}$ 筛的适用条件：$F(p)$ 的值可以拆分为若干个完全积性函数，且 $F(p^k)$ 可以快速计算。
+首先给定 $\text{Min_25}$ 筛的适用条件：$F(p)$ 的值可以拆分为若干个完全积性函数 $f(p)$，且 $\sum f(x)$ 可以快速计算。
 设 $\text{midv}(x)$ 表示 $x$ 的最小素因子。将所有素数从小到大排列，记为 $p_1,p_2,p_3\cdots$
@@ 行 35: / 行 35: @@
 使用刷表法暴力转移上述方程直到 $p_{k+1}^2\gt n$，此时得到 $g(a,k)=\sum_{i=1}^a[i\in \text{prime}]f(i)=\sum_{i=1}^a[i\in \text{prime}]F(i),a\in \lfloor \frac nx\rfloor$。
-不妨将此时的 $g(n,k)$ 记为 $g(n)$。由于玄学因素，该过程的时间复杂度为 $O(\frac {n^{\frac 34}}{\log n})$。
+不妨将此时的 $g(n,k)$ 记为 $g(n)$。由于玄学因素，该过程的时间复杂度为 $O\left(\frac {n^{\frac 34}}{\log n}\right)$。
 接下来设 $S(n,k)=\sum_{i=1}^n[mdiv(i)\gt p_k]F(i)$，于是目标就是求 $S(n,0)+F(1)=S(n,0)+1$(积性函数必有 $F(1)=1$)。
@@ 行 47: / 行 47: @@
 最后补上 $F(p_i^j)[j\neq 1]$ 是因为 $F(p_i^j)S(\lfloor\frac n{p_i^j}\rfloor,i)$ 不包含 $F(p_i^j)$ 的贡献，但 $F(p_i)$ 的贡献已经计算。
-由于 $p_i^2\gt n$ 时 $\sum_{p_i^j\le n}F(p_i^j)(S(\lfloor\frac n{p_i^j}\rfloor,i)+[j\neq 1])=0$，于是只需要枚举 $O(\frac {\sqrt n}{\log n})$ 个素数即可。
+由于 $p_i^2\gt n$ 时 $\sum_{p_i^j\le n}F(p_i^j)(S(\lfloor\frac n{p_i^j}\rfloor,i)+[j\neq 1])=0$，于是只需要枚举 $O\left(\frac {\sqrt n}{\log n}\right)$ 个素数即可。
-由于玄学因素，该过程不需要记忆化且时间复杂度为 $O(\frac {n^{\frac 34}}{\log n})$。
+由于玄学因素，该过程不需要记忆化且时间复杂度为 $O\left(\frac {n^{\frac 34}}{\log n}\right)$。
 ==== 算法例题 ====
@@ 行 142: / 行 142: @@
 === 例题二 ===
-[[https://loj.ac/problem/6053|LOJ5325]]
+[[https://loj.ac/problem/6053|LOJ6053]]
 == 题意 ==
@@ 行 237: / 行 237: @@
 先将 $S(n,k)$ 分为素数贡献和合数贡献。显然素数贡献为 $0$，故只考虑合数贡献。
-枚举合数的最小素因子，于是可以将合数分为最小素因子等于次大素因子的数和最小素因子不等于次大素因子的数。
+将合数分为最小素因子等于次大素因子的数和最小素因子不等于次大素因子的数，枚举合数的最小素因子及其幂次。
-对于最小素因子不等于次大素因子的数，考虑枚举其最小素因子的幂次，然后将最小素因子直接提取出来，显然这不会影响这些数的次大素因子。
+对于最小素因子不等于次大素因子的数，将最小素因子的全部幂次直接提取出来，显然这不会影响这些数的次大素因子，该类数的贡献为
-该类数的贡献为
 $$\sum_{i=k+1}^{p_i^2\le n}\sum_{p_i^j\le n}^nS(\lfloor\frac n{p_i^j}\rfloor,i)$$
-而对于最小素因子等于次大素因子的数
+而对于最小素因子等于次大素因子的数，它一定可以写成 $p_i^jp_x(x\ge i)$ 的形式，于是该类数的贡献为
+$$\sum_{i=k+1}^{p_i^2\le n}\sum_{p_i^{j+1}\le n}(g(\lfloor\frac n{p_i^j}\rfloor)-i+1)$$
+于是可以得到式子
+$$S(n,k)=\sum_{i=k+1}^{p_i^2\le n}\sum_{p_i^j\le n}^n\left(S(\lfloor\frac n{p_i^j}\rfloor,i)+\max(g(\lfloor\frac n{p_i^j}\rfloor)-i+1,0)\right)$$
+<hidden 查看代码>
+<code cpp>
+const int MAXN=sqrt(1e11)+10;
+namespace Min_25{
+	LL n,blk[MAXN<<1],g[MAXN<<1];
+	int sqr,vis[MAXN],prime[MAXN],p_cnt;
+	int b_cnt,idx1[MAXN],idx2[MAXN];
+	int id(LL x){return x<=sqr?idx1[x]:idx2[n/x];}
+	LL S(LL a,int b){
+		if(a<=prime[b])return 0;
+		LL ans=0;
+		for(int i=b+1;i<=p_cnt&&1LL*prime[i]*prime[i]<=a;i++){
+			LL pow_p=prime[i];
+			for(int j=1;pow_p<=a;j++){
+				ans=ans+prime[i]*max(0LL,g[id(a/pow_p)]-i+1)+S(a/pow_p,i);
+				pow_p*=prime[i];
+			}
+		}
+		return ans;
+	}
+	LL cal(LL n){
+		Min_25::n=n;
+		sqr=sqrt(n+0.5);
+		b_cnt=p_cnt=0;
+		for(int i=2;i<=sqr;i++){
+			if(!vis[i])prime[++p_cnt]=i;
+			for(int j=1;j<=p_cnt&&i*prime[j]<=sqr;j++){
+				vis[i*prime[j]]=1;
+				if(i%prime[j]==0)break;
+			}
+		}
+		for(LL lef=1,rig=0;lef<=n;lef=rig+1){
+			rig=n/(n/lef);
+			blk[++b_cnt]=n/lef;
+			g[b_cnt]=blk[b_cnt]-1;
+			if(blk[b_cnt]<=sqr)
+			idx1[blk[b_cnt]]=b_cnt;
+			else
+			idx2[rig]=b_cnt;
+		}
+		_rep(i,1,p_cnt){
+			LL pow_p=1LL*prime[i]*prime[i];
+			for(int j=1;j<=b_cnt&&blk[j]>=pow_p;j++){
+				int pos=id(blk[j]/prime[i]);
+				g[j]=g[j]-(g[pos]-i+1);
+			}
+		}
+		return S(n,0);
+	}
+}
+int main()
+{
+	LL L=read_LL(),R=read_LL();
+	enter(Min_25::cal(R)-Min_25::cal(L-1));
+	return 0;
+}
+</code>
+</hidden>
+=== 例题四 ===
+[[https://loj.ac/problem/6682|LOJ6682]]
+== 题意 ==
+$$\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n[(j\mid i)\text{ and }((j+k)\mid i)]$$
+== 题解 ==
+$$\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n[(j\mid i)\text{ and }((j+k)\mid i)]=\sum_{i=1}^n\sum_{j=1}^n\sum_{k=j+1}^n[(j\mid i)\text{ and }(k\mid i)]=\sum_{i=1}^n{\tau (i)\choose 2}$$
+考虑 $i$ 作为因子对 $\lfloor\frac ni\rfloor$ 个数产生了贡献，于是 $\sum_{i=1}^n\tau(i)=\sum_{i=1}^n\lfloor\frac ni\rfloor$，可以整数分块解决。
+记 $F(i)=\tau^2(i)$，则 $f(p)=4$，套 $\text{Min_25}$ 筛即可。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5,Mod=998244353,inv2=(Mod+1)/2;
+namespace Min_25{
+	LL n,blk[MAXN<<1];
+	int sqr,vis[MAXN],prime[MAXN],p_cnt,g[MAXN<<1];
+	int b_cnt,idx1[MAXN],idx2[MAXN];
+	int S(LL a,int b){
+		if(a<=prime[b])return 0;
+		int pos=(a<=sqr)?idx1[a]:idx2[n/a];
+		int ans=(g[pos]-4LL*b)%Mod;
+		for(int i=b+1;i<=p_cnt&&1LL*prime[i]*prime[i]<=a;i++){
+			LL pow_p=prime[i];
+			for(int j=1;pow_p<=a;j++){
+				ans=(ans+1LL*(j+1)*(j+1)%Mod*(S(a/pow_p,i)+(j!=1)))%Mod;
+				pow_p*=prime[i];
+			}
+		}
+		return (ans+Mod)%Mod;
+	}
+	int cal(LL n){
+		Min_25::n=n;
+		sqr=sqrt(n+0.5);
+		for(int i=2;i<=sqr;i++){
+			if(!vis[i])prime[++p_cnt]=i;
+			for(int j=1;j<=p_cnt&&i*prime[j]<=sqr;j++){
+				vis[i*prime[j]]=1;
+				if(i%prime[j]==0)break;
+			}
+		}
+		for(LL lef=1,rig=0;lef<=n;lef=rig+1){
+			rig=n/(n/lef);
+			blk[++b_cnt]=n/lef;
+			g[b_cnt]=(blk[b_cnt]-1)%Mod;
+			if(blk[b_cnt]<=sqr)
+			idx1[blk[b_cnt]]=b_cnt;
+			else
+			idx2[rig]=b_cnt;
+		}
+		_rep(i,1,p_cnt){
+			LL pow_p=1LL*prime[i]*prime[i];
+			for(int j=1;j<=b_cnt&&blk[j]>=pow_p;j++){
+				LL pos=blk[j]/prime[i];
+				pos=(pos<=sqr)?idx1[pos]:idx2[n/pos];
+				g[j]=(g[j]-(g[pos]-(i-1)))%Mod;
+				g[j]=(g[j]+Mod)%Mod;
+			}
+		}
+		_rep(i,1,b_cnt)
+		g[i]=g[i]*4LL%Mod;
+		return (S(n,0)+1)%Mod;
+	}
+}
+int cal(LL n){
+	LL lef=1,rig;
+	int ans=0;
+	while(lef<=n){
+		rig=n/(n/lef);
+		ans=(ans+1LL*(n/lef)*(rig-lef+1))%Mod;
+		lef=rig+1;
+	}
+	return ans;
+}
+int main()
+{
+	LL n=read_LL();
+	enter(1LL*(Min_25::cal(n)-cal(n)+Mod)*inv2%Mod);
+	return 0;
+}
+</code>
+</hidden>
+=== 例题五 ===
+== 题意 ==
+设 $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$，则 $f(n)=\alpha_1+\alpha_2+\cdots \alpha_k$，求
+$$\sum_{i=1}^nf(i!)$$
+== 题解 ==
+发现 $f(ab)=f(a)+f(b)$，于是
+$$\sum_{i=1}^nf(i!)=\sum_{i=1}^n\sum_{j=1}^if(j)=\sum_{i=1}^n(n-i+1)f(i)=(n+1)\sum_{i=1}^nf(i)-\sum_{i=1}^nif(i)$$
+不妨将 $p^k$ 对 $f(n)$ 的贡献分配给 $p,p^2\cdots p^k$，于是
+$$(n+1)\sum_{i=1}^nf(i)-\sum_{i=1}^nif(i)=\sum_{i=1}^{p_i\le n}\sum_{k=1}^{p_i^k\le n}(n+1)\lfloor\frac n{p_i^k}\rfloor-\frac {\lfloor\frac n{p_i^k}\rfloor(\lfloor\frac n{p_i^k}\rfloor+1)}{2}p_i^k$$
+对 $k\ge 2$ 的情况，暴力计算时间复杂度 $O(\sum_{k=2}^{2^k\le n}n^{\frac 1k})\approx O(\sqrt n)$。
+对 $k=1$，则需计算
+$$\sum_{i=1}^{p_i\le n}(n+1)\lfloor\frac n{p_i}\rfloor-\frac {\lfloor\frac n{p_i}\rfloor(\lfloor\frac n{p_i}\rfloor+1)}{2}p_i$$
+通过 $\text{Min_25}$ 筛计算出 $g_1(n)=\sum_{i=1}^n[i\in \text{prime}],g_2(n)=\sum_{i=1}^n[i\in \text{prime}]i$。
+最后考虑整数分块，发现一个块的贡献为 $(g_1(r)-g_1(l-1))(n+1)\lfloor\frac n{p_i}\rfloor-(g_2(r)-g_2(l-1))\frac {\lfloor\frac n{p_i}\rfloor(\lfloor\frac n{p_i}\rfloor+1)}{2}p_i$。
+$g(r)-g(l-1)$ 恰好为 $\text{Min_25}$ 筛的相邻块，可以直接计算。总时间复杂度 $O\left(\frac {n^{\frac 34}}{\log n}\right)$。

CVBB ACM Team

用户工具

站点工具

差别

页面工具