[蓝桥杯 2023 国 B] 双子数

[蓝桥杯 2023 国 B] 双子数

B 双子数

若一个正整数 $x$ 可以被表示为 $p^2\times q^2$，其中 $p$、$q$ 为质数且 $p\ne q$，则 $x$ 是
一个 “双子数”。请计算区间 $[2333,23333333333333]$ 内有多少个 “双子数”？

输入格式

输入一个大写字母，表示第几个问题。

输出格式

根据所输入的问题编号，输出对应问题的答案。

答案：
947293

知识点1：
判断素数（欧式筛选）

//1.定义最大上限
const int n=10000010;
//2.定义判断素数数组，1：不是素数 0：是素数
bool f[n]={1,1};//0,1不素数
//3.定义动态数组：储存素数
vector<int> v;
//4.找素数
for(int i=2;i<=n;i++) //第一次循环枚举 2~n的数
  {
  	
  	if(f[i]!=1) // 如果是素数，放进数组里面
  	v.push_back(i);
  	for(int j=0;j<v.size()&&i*v[j]<=n;j++)//i*v[j] 不能超过上限
  	
  	/*j是枚举现在找到的素数，假如有一个素数是a,
	  我们要标记的是 2*a,3*a,4*a,5*a一定不是素数
	  而前面的系数就是我们枚举的i,素数就是遍历数组得到的v[j]
	   i*v[j] 标记的合数 	  
	  */
  	
  	{
  		f[i*v[j]]=1;
  		if(i%v[j]==0)break; //120=2*3*20 
		  //有两个质因子 2，3 我们仅仅需要标记最小的那个 如果能被整除 就跳出循环  
  		
  		
	  }
  }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

埃式筛选：

//埃氏筛法
int n=1e5;
bool shai[n];
//vector<int >shai;
int cun[n];
signed main()
{
    int cnt = 0;
    //如果你用的是vector,则进行注释部分操作
    //shai.push_back(1), shai.push_back(1);//在0,1两个位置先添加。0，1都不是素数所以都添1。
    //for (int i = 2; i <= n; i++)
    //{
    //    shai.push_back(0);
    //}
    for (int i = 2; i <= n; i++)
    {
        if (!shai[i])//如果没有被标记
        {
            cun[cnt++] = i;
            for (int j = 2; j <= n; j++)
            {
                if (i * j > n)break;//超过数据大小就退掉。
                shai[i * j] = 1;//1标记的都是素数的倍数——所以不是素数。
            }
        }
    }
    for (int i = 0; i < cnt; i++)
    {
        printf("%d ", cun[i]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

欧式筛选和埃式筛选

代码：

#include <bits/stdc++.h>
#define int __int128 //用__int128稳一点 
using namespace std;

long long ans=0;
const int n=10000010;
bool f[10000010]={1,1}; //标记
vector<int> v;
signed main(){
	for(int i=2;i<=n;i++)
	{
		if(f[i]!=1)  
		v.push_back(i);
		for(int j=0;j<v.size()&&v[j]*i<=n;j++)
		{
			f[v[j]*i]=1;
			if(i%v[j]==0)break;
		}
	}
for(int i=0;i<v.size();i++)
  for(int j=i+1;j<v.size();j++)
  {
  	 if(v[i]*v[i]*v[j]*v[j]<2333)continue;
     else  if(v[i]*v[i]*v[j]*v[j]>23333333333333)break;
  	 ans++;
  }
	

	cout<<ans<<endl; 
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

疑惑一：

我重命名 int为long long 结果错误

错误答案：947303 而题解定义为__int128:答案正确