当前位置：首页 > news >正文

遣其欲，而心自静 -- 33DAI

news 2025/7/24 4:59:58

显然，死做枚举只能的50分。

错了4次总算对了。

大体思路：

因题目说只有两个因数，那么有两种情况：

1：两个质数相乘，如：3*5=15 5*7=45 等（不包括5*5=25 或5*3=15 重复计算\ 因为3*5算了/）

2：（特别容易忽略） $x^{3}$ （注： $x$ 为质数）

我是这样编的：

1.剪枝筛选（算出质数）

2.for(i=1;i<=n;i++) if(是质数) 保存。

3.枚举质数个数，判断能和几个数进行质数相乘且<=n（二分）答案+=个数-i

4.判断 $x^{3}$ （注： $x$ 为质数）答案++

5.cout

易错点：保存质数的数组要 $long long$

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
int n,i,f[10000100],j;long long b[5000010];
int sum,t,w,mid,bao,ans;
main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin>>n;f[1]=1;
    for(i=4;i<=n;i+=2)f[i]=1;
    for(i=3;i<=sqrt(n);i++)
        if(f[i]==0)for(j=i*2;j<=n;j+=i)f[j]=1;//剪枝筛选
    for(i=2;i<=n;i++)
        if(f[i]==0)b[++sum]=i;//个数
    for(i=1;i<=sum;i++){
        t=i+1;w=sum;bao=0;
        while(t<=w){
            mid=(t+w)/2;
            if(b[mid]*b[i]<=n) t=mid+1,bao=mid;
            else w=mid-1;
        }//二分
        if(bao==0)break;//优化
        else{
            ans+=bao-i;//答案+=格式-i（-i是去重）
        }
    }
    for(i=2;i*i*i<=n;i++)//3次方的加加
        if(f[i]==0)ans++;
    cout<<ans;
}

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
int n,i,f[10000100],j;long long b[5000010];
int sum,t,w,mid,bao,ans;
main(){ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cin>>n;f[1]=1;for(i=4;i<=n;i+=2)f[i]=1;for(i=3;i<=sqrt(n);i++)if(f[i]==0)for(j=i*2;j<=n;j+=i)f[j]=1;//剪枝筛选for(i=2;i<=n;i++)if(f[i]==0)b[++sum]=i;//个数for(i=1;i<=sum;i++){t=i+1;w=sum;bao=0;while(t<=w){mid=(t+w)/2;if(b[mid]*b[i]<=n) t=mid+1,bao=mid;else w=mid-1;}//二分if(bao==0)break;//优化else{ans+=bao-i;//答案+=格式-i（-i是去重）}}for(i=2;i*i*i<=n;i++)//3次方的加加if(f[i]==0)ans++;cout<<ans;
}

查看全文

http://www.lryc.cn/news/500027.html