一个步骤: 在[ a, b] 中标记 S 的倍数
#include<iostream> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int N=1e5+20; const int Q=2e9+2; #define int long long bool vis[Q]; int b[N], pm[N],tot=0; void init(int top){ b[1]=1; for(int i=2;i<=top;i++){ if(b[i]) continue; pm[++tot]= i; for(int j=2;j*i<=top;j++) b[j*i]=1; } } void sov () { vector<int> vec; int ret = 0; int a, b, s, k; memset(vis, 0, sizeof(vis)); cin>>a>>b>>k>>s; // 对于质数I, 筛出[a,b] 之间I 的倍数 for (int i =1; i <=tot && pm[i] * pm[i] <= b; i++) { int u = pm[i];int d = (u - a % u) % u; if (u == a + d) d += u; while (d <= b - a) { vis[d] = 1; d += u; } } for (int i = 0; i <= b-a; i++) { if (vis[i] == 0 && a + i > 1) vec.push_back(a+i); } for (int i = 0; i + k - 1 < vec.size(); i++) { if (vec[i+k-1] - vec[i] == s) ret++; } cout<<ret<<endl; } signed main () { init(1e5); int cas; cin>>cas; while (cas--) sov(); }
标签:Prime,const,int,vis,vec,UVA,include,1404 From: https://www.cnblogs.com/towboa/p/17349297.html