2018.08.29 NOIP模拟 pmatrix(线性筛)
2024-09-24 09:04:06
【问题描述】
根据哥德巴赫猜想(每个不小于 6 的偶数都可以表示为两个奇素数之和),定义
哥德巴赫矩阵 A 如下:对于正整数对(i,j),若 i+j 为偶数且 i,j 均为奇素数,则 Ai,j = 1,
否则 Ai,j = 0。现在有若干询问(x1,y1,x2,y2),你需要回答下列式子的值
【输入】
第一行一个整数 m
接下来 m 行,每行四个整数 x1 y1 x2 y2,表示一个询问
【输出】
m 行,每行一个整数,表示对应询问的答案
【输入样例】
1
1 1 3 5
【输出样例】
2
30%的数据保证 x2, y2, m ≤ 100
100%的数据保证 1 ≤ x1 ≤ x2 ≤ 10^6; 1 ≤ y1 ≤ y2 ≤ 10^6; m ≤ 1000
签到题。
一开始题读错了。。。
差点忘记开long long。。。
就是线性筛之后维护一个素数出现次数的前缀和。
代码:
#include<bits/stdc++.h>
#define N 1000005
#define ll long long
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int pri[N],tot=0;
ll cnt[N];
bool vis[N];
inline void init(int len){
vis[1]=true;
for(int i=2;i<=len;++i){
if(!vis[i])pri[++tot]=i;
for(int j=1;j<=tot;++j){
if(pri[j]*i>len)break;
vis[pri[j]*i]=1;
if(i%pri[j]==0)break;
}
}
for(int i=3;i<=len;++i)cnt[i]=vis[i]?cnt[i-1]:cnt[i-1]+1ll;
}
int main(){
// freopen("pmatrix.in","r",stdin);
// freopen("pmatrix.out","w",stdout);
init(1000000);
int m=read();
while(m--){
int a=read()-1,c=read()-1,b=read(),d=read();
cout<<(cnt[b]-cnt[a])*(cnt[d]-cnt[c])<<'\n';
}
return 0;
}
最新文章
- tomcat8 配置在线管理应用功能
- maven加载jar包配置
- C#之发送邮件汇总
- 图片上传和显示——上传图片——上传文件)==ZJ
- HTML5前端(移动端网站)性能优化指南
- 模糊系统架构和简单实现--AForge.NET框架的使用(四)
- Ffmpeg和SDL如何同步视频(转)
- Thinkphp 3.2中文章详情页的上一篇 下一篇文章功能
- Xcode无法安装基于ruby的插件问题的解决
- java中的Condition协作线程接口类
- IntelliJ IDEA(四) :Settings(上)
- 创建一个UWP 打包签名
- Linux:command not found
- MT【37】二次函数与整系数有关的题
- DbUtil数据库连接
- java 递归 树形
- python 穷举法 算24点(史上最简短代码)
- FallbackFactory启动的时候抛出异常
- <;[完整版]中国式价值投资>;读书笔记
- xcrun: error: invalid active developer path (/Applications/Xcode.app/Contents/Developer)解决办法