双子数
题目 双子数
思路分析
想法是先筛出要用的素数 再来个二重循环枚举
要用的素数大概有多少个 直接23333333333333显然是不可能的
\(x=p^2\times q^2\)，所以最大的 \(p\) 和 \(q\) 应该满足 \(p^2\times q^2\le 23333333333333\)
考虑到最小化的情况，即 \(p=q\) 时取 \(x\) 的最大值 \(p^4=23333333333333\)
直接取 \(\\sqrt{23333333333333}=4,830,458\)
另外 考虑到long long可能也溢出 将int 替换成 __int128
那么涉及输入输出就别用int128了 不然得重新写print函数
要输出的cnt 用long long 就行
代码实现
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int __int128
const int N=4830458;
typedef long long LL;
bool st[N];
vector<int> primes;
void get_primes(){
for(int i=2;i<=N;i++){
if(!st[i]){
primes.push_back(i);
for(int j=i;j<=N;j+=i)
st[j]=true;
}
}
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
get_primes();
LL cnt=0;
for (int i = 0; i < primes.size(); i++) {
for (int j = i + 1; j < primes.size(); j++) {
int p = primes[i], q = primes[j];
int product = p * p * q * q;
if (product < 2333) continue;
if (product > 23333333333333) break;
cnt++;
}
}
cout<<cnt;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
// 2333,23333333333333 sqrt一下：4830458.9153964450212949209345558 筛出这个范围的素数就差不多了
#define int __int128
typedef long long LL;
const int N=4830458;
bool st[N];
int primes[N],cnt;
void get_prime(){
for(int i=2;i<=N;i++){
if(!st[i])
primes[cnt++]=i;{
for(int j=i;j<=N;j+=i)
st[j]=true;
}
}
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
get_prime();
LL res=0;
for(int i=0;i<cnt;i++){
for(int j=i+1;j<cnt;j++){
int p=primes[i],q=primes[j];
int tmp=p*p*q*q;
if(tmp<2333) continue;
if(tmp>23333333333333) break;
res++;
}
}
cout<<res<<endl;
return 0;
}
💬 评论