差别

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

--- 2020-2021:teams:legal_string:jxm2001:数论_4 [2020/09/22 15:20]
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]]
 == 题意 ==
@@ 行 309: / 行 309: @@
 </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

用户工具

站点工具

差别

页面工具