x02 北京2 d1 下午课程
2024-07-22 18:50:15
发布于：北京
5阅读
0回复
0点赞
枚举算法：
将问题所有的可能结果一一列举
定义一个常量：
const int N=1e5+100
前缀和：
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m,l,r,a[100005],s[100005];
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
s[i]=s[i-1]+a[i];
}
cin>>m;
while(m--){
cin>>l>>r;
cout<<s[r]-s[l-1]<<endl;
}
return 0;
}
（此代码为T3题解，仅供参考）
埃氏筛与线式筛：
埃氏筛：把不大于根号N的所有素数的倍数全部剔除。
#include<iostream>
using namespace std;
const int MAXN=4000005;
int r,cnt,s;
int prime[MAXN];
bool isp[MAXN]={true,true};
int main(){
for(int i=2;i<=MAXN;i++){
if(!isp[i]) prime[++cnt]=i;
for(int j=1;prime[j]*i<=MAXN&&j<=cnt;j++){
isp[prime[j]*i]=true;
if(i%prime[j]==0) break;
}
}
cin>>r;
for(int l=1;l<=r;l++) if(!isp[l]) s++;
cout<<s;
return 0;
}
（此代码为T5题解，仅供参考）
线性筛：
2~n之间的每个数
#include<bits/stdc++.h>
using namespace std;
const int N=100000000+100;
int prime[N],vis[N],cnt;
int main(){
int n;
cin>>n;
vis[1]=1;
for(int i=2;i<=n;i++){
if(!vis[i])prime[cnt++]=i;
for(int j=0;j<cnt&&i*prime[j]<=n;j++){
vis[i*prime[j]]=1;
if(i%prime[j]==0)break;
}
}
int cnt=0;
for(int i=1;i<=n;i++)cnt+=(vis[i]==false);
cout<<cnt;
return 0;
}
（此代码为T6题解，仅供参考）
c++开根号：
sqrt（）
（头文件#include<cmath>）
这里空空如也
有帮助，赞一个