两道都是填空题

填空题在本地运行，所以时间复杂度较为宽松。只要代码能跑出来即可。

题目： https://www.luogu.com.cn/problem/P9420

子2023

思路：DP

记录到目前为止，子序列“2”、“20”、“202”和“2023”的个数。注意理解到目前为止。这样，在遍历大字符串的时候，每遇到一个字符，一定可以接在相关字符的后面，组成新的字符。因为记录的子序列一定是之前出现的，这个新的字符一定是出现在子序列之后的。

Code

#include<iostream>
#include<string>
using namespace std;

typedef long long ll;
string s;

int main()
{
    for(int i = 1; i <= 2023; i ++)
        s += to_string(i);
    int n = s.size();

    ll n2 = 0, n20 = 0, n202 = 0, n2023 = 0;
    for(int i = 0; i < n; i ++)
    {
        if(s[i] == '2')
        {
            n2++;
            //对于新出现的一个2，可以接在之前的序列20的后面，组成202
            n202 += n20;
        }
        else if(s[i] == '0')
        {
            n20 += n2; //同理，0可以接在之前2的后面，组成20
        }
        else if(s[i] == '3')
        {
            n2023 += n202;
        }
    }
    printf("%lld",n2023);
    return 0;
}

双子数

思路：线性筛+暴力枚举

1. 范围的确定
   使用自带的计算器得到 23333333333333 开方为 4830458，所以筛素数的范围设置为5e6一定是够用的。
2. 暴力枚举
   这里暴力枚举感觉还是有点小优化的。不是从 233——23333333333333 范围内进行枚举，而是直接枚举质数的平方之积，使用 if 条件判断筛选出合适的答案。
3. __int128类型的使用
   这道题目中，N范围内，四个质数的乘积会爆long long，所以使用_int128来存储大整数。__int128devC++上兼容扩展，其最大可以存储 $10^{38}$ 的整数。

Code

#include<iostream>
#include<cstdio>
#include<unordered_map>
using namespace std;
//4,830,458

typedef long long ll;
const int N = 5e6;

int prime[N],cnt; //筛质数
bool sta[N];

unordered_map<ll,bool> mp; //记录范围内的双子数

int main()
{
    for(int i = 2; i <= N; i ++) //筛出1——N范围内的质数
    {
        if(sta[i] == false) //如果i没有被筛去（i不是合数）
            prime[cnt++] = i;

        for(int j = 0; prime[j]<=N/i; j ++)
        {
            sta[prime[j]*i] = true;

            if(i % prime[j] == 0)
                break;
        }
    }
//  printf("%d ",cnt);

    for(int i = 0; i < cnt; i ++)
    {
        __int128 p = prime[i];
        for(int j = i+1; j < cnt; j ++)
        {
            __int128 q = prime[j];

            __int128 res = p*p*q*q;
            if(res > 23333333333333)
                break;
            else if(res < 2333)
                continue;
            else
                mp[res] = true;
        }
    }
    ll ans = mp.size();
    printf("%lld",ans);
    return 0;
}