自动搬运

查看原文

来自洛谷，原作者为

	zhlzt Light in the eyes.

搬运于2025-08-24 22:48:12，当前版本为作者最后更新于2023-06-23 14:37:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

第一题 DP 做法

其实第一题并不难，我们设在 $s$ 的截止到当前位置的前缀字符串中，为 $2,20,202,2023$ 的子序列分别有 $dp_{0},dp_{1},dp_{2},dp_{3}$ 个，那么不难推出，$dp_{0},dp_{1},dp_{2},dp_{3}$ 要用以下规则更新：

• 若当前数字为 $2$，可以单独作一个子序列，即 $dp_{0}\gets dp_{0}+1$，也可以接在子序列 $20$ 之后构成 $202$，即 $dp_{2}\gets dp_{2}+dp_{1}$。
• 若当前数字为 $0$，可以接在子序列 $2$ 之后构成 $20$，即 $dp_{1}\gets dp_{1}+dp_{0}$。
• 若当前数字为 $3$，可以接在子序列 $202$ 之后构成 $2023$，即 $dp_{3}\gets dp_{3}+dp_{2}$。

最后答案就是为 $2023$ 的子序列的数量 $dp_{3}$。

第二题埃氏筛与暴力枚举做法

第二题更水，直接埃氏筛求素数，再暴力枚举 $p,q$，剪枝优化即可，具体见代码注释。

需要注意的是，由于 $p,q$ 的平方都不超过 $23333333333333$，所以这里埃氏筛只需要筛到 $\sqrt{23333333333333}$，约 $5\times 10^6$，其实还可以再缩小，因为 $p,q$ 中较小的数的平方至少为 $4$（值为 $2$ 时取到），此时另一个数最多还不到 $2.5\times10^6$，开个 $3\times 10^6$ 就已经够保险了。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=5e6;
long long dp[5]; string s;
int isprime[N+10],prime[N+10];  
int main(){
	if(getchar()=='A'){
		for(int i=1;i<=2023;i++) s+=to_string(i);
		// to_string(i) 是将 i 变为字符串
		// s+=t 代表将字符串 t 添加到 s 末尾 
		for(int i=0;i<s.size();i++){
			if(s[i]=='2') dp[0]++,dp[2]=dp[2]+dp[1];
			else if(s[i]=='0') dp[1]=dp[1]+dp[0];
			else if(s[i]=='3') dp[3]=dp[3]+dp[2];
		}
		printf("%lld",dp[3]);
	}
	else{ 
		int cnt=0,ans=0;
		for(int i=2;i<=sqrt(N);i++){
			if(!isprime[i]){
				for(int j=i*i;j<=N;j+=i) isprime[j]=1;
			}
		}
		for(int i=2;i<=N;i++){ 
			if(!isprime[i]) prime[++cnt]=i;
		}
		for(int i=1;i<=cnt;i++){
			long long p2=1LL*prime[i]*prime[i];
			if(1LL*p2*p2>23333333333333) break;
			for(int j=i+1;j<=cnt;j++){
				long long q2=1LL*prime[j]*prime[j];
				if(1LL*p2*q2<2333) continue;
				// p*p*q*q 太小，不能更新答案 
				if(1LL*p2*q2>23333333333333) break; 
				ans++;
			}
		}
		printf("%d",ans); 
	}
	return 0;
}