題目描述

如果把一年之中的某個時間寫作 a 月 b 日 c 時 d 分 e 秒的形式，當這五個數都為質數時，我們把這樣的時間叫做質數時間，現已知起始時刻是 2022 年的 a 月 b 日 c 時 d 分 e 秒，終止時刻是 2022 年的 u 月 v 日 w 時 x 分 y 秒，請你統計在這段時間中有多少個質數時間?

輸入

輸入共 (2?T+1) 行。第一行一個整數 T ，代表共有 T 組查詢。
接下來2?T 行，對于每組查詢，先輸入一行五個整數a、b、c、d、e ，代表起始時刻是 a 月 b 日 c 時 d 分 e 秒。再輸入一行五個整數u、v、w、x、y，代表終止時刻是 u 月 v 日 w 時 x 分 y 秒。
對于每組查詢保證輸入的起始時刻不晚于終止時刻。

輸出

輸出共 T 行，一行一個整數，表示對于每組查詢輸入統計到的從 a 月 b 日 c 時 d 分 e 秒到 u 月 v 日 w 時 x 分 y 秒中質數時間的個數。多組查詢結果用換行分隔。

樣例輸入

3
3 3 3 3 0
3 3 3 5 59
7 2 6 45 32
7 29 15 30 54
2 6 2 45 32 
12 3 16 56 8

樣例輸出

34
24276
127449

提示

對于所有數據，保證1≤T≤105 且1≤a,u≤12, 1≤b, 1≤b,v≤31, 0≤c,w<24, 0≤d,x<60 ,0≤e,y<60。
每個測試點的數據規模及特點如下表所示。

思路分析

1.預處理所有質數時間，轉化為秒，存入數組。

2.讀入數據，同樣地，將起止時間轉化為秒，二分查找。（起點對應lower_bound，終點對應upper_bound。lower_bound返回第一個指向不小于value的數的位置的迭代器，upper_bound返回第一個指向大于value的數的位置的迭代器。）

代碼

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll T;
vector<int>month={2,3,5,7,11};
vector<int>day={2,3,5,7,11,13,17,19,23,29,31};
vector<int>hour={2,3,5,7,11,13,17,19,23};
vector<int>ms={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59};
vector<ll>p;
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);vector<int>v={31,28,31,30,31,30,31,31,30,31,30,31};vector<vector<int>>data(15,vector<int>(35,0));ll k=0;for(int i=0;i<12;i++){for(int j=1;j<=v[i];j++){data[i+1][j]=k;k++;}}for(int i=0;i<5;i++){for(int j=0;j<11;j++){if(month[i]==2&&day[j]>28)break;if(month[i]==11&&day[j]>30)break;for(int k=0;k<9;k++){for(int m=0;m<17;m++){for(int n=0;n<17;n++){ll t=data[month[i]][day[j]]*24*60*60+hour[k]*60*60+ms[m]*60+ms[n];p.push_back(t);}}}}}cin>>T;while(T--){ll t,ans=0;int a,b,c,d,e,u,v,w,x,y;cin>>a>>b>>c>>d>>e;cin>>u>>v>>w>>x>>y;ll st=data[a][b]*24*60*60+c*60*60+d*60+e;ll ed=data[u][v]*24*60*60+w*60*60+x*60+y;auto it=lower_bound(p.begin(),p.end(),st);auto id=upper_bound(p.begin(),p.end(),ed);ans=id-it;cout<<ans<<"\n";}return 0;
}

（若定義vector<ll> p(35000000,0);p數組的大小為35000000個long long，每個long long8字節，總大小約35000000*8=280,000,000字節，即280MB）