首页 > 其他分享 >Prime k-tuple UVA - 1404

Prime k-tuple UVA - 1404

时间:2023-04-24 14:15:12浏览次数:43  
标签:Prime const int vis vec UVA include 1404

 

    一个步骤:  在[ 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

相关文章

  • The Bells are Ringing UVA-12119
    已知M为T1,T2,T3的LCM输出满足Ti-Tj<=25的所有可能情况#include<iostream>#include<cmath>#include<algorithm>#include<cstring>usingnamespacestd;constintN=1E6+3;#defineintlonglongintpm[N],tot;intb[N],fac[N],F[N],len,cnt[N]......
  • UVA11014
     给定一个NxNxN的正方体,求出最多能选几个整数点。使得随意两点PQ不会使PQO共线。  F(k)#include<iostream>#include<cmath>#include<algorithm>usingnamespacestd;constintN=5e5;#defineintlonglongintb[N+2],pm[N+2],tot=0;intn;intpow3(intx){......
  • Gauss Prime UVA - 1415
     #include<iostream>#include<cstring>#include<algorithm>usingnamespacestd;constintN=5e4;intb[N+2],pm[N+2],tot=0;voidinit(){b[1]=1;for(inti=2;i<=N;i++){if(b[i])continue;pm[++tot]=i;......
  • 【CMU15-445 FALL 2022】Project #0 - C++ Primer
    关于参考&鸣谢课程官网CMU15445vscode/clionclang12cmake环境配置C++调试窗口显示“forstringvariable【CMU15-445数据库】bustubProject#0:Trie树实现(C++Primer)2022CMU15-445学习群——152391370前言按照课程要求,本文并不会给出实现代码,可以当做是我遇到问题的总......
  • Counting Rectangles UVA - 10574
    给出n个点。问选出4个点作为定点,能够组成多少个平行与坐标轴的矩形。 点按照x排序 n^2挑选出垂直x轴的线段,按照y1排序  #include<iostream>#include<cstring>#include<algorithm>#include<vector>usingnamespacestd;constintN=1e5;structT{ intx......
  • Eigensequence UVA - 11133
    给你一个递增序列的第一位a1,最后一位an,求有多少个序列满足:以a1为首,an为尾 1、B(1)=A(1)2、后面每项满足A[j]=B[j], A(j-1)<B(j)≤A(j),且bj能整除A(j)-A(j-1)。   F[i][j]最后一位为j的方案数#include<iostream>#include<cstring>#include<a......
  • UVA Children’s Game(贪心)
    Description4thIIUCInter-University ProgrammingContest,2005AChildren’sGameInput:standardinputOutput:standardoutputProblemsetter: Md. KamruzzamanTherearelotsofnumbergamesforchildren.Thesegamesareprettyeasytoplaybutnotsoeasyt......
  • UVA Immediate Decodability(简单字典树)
    ImmediateDecodabilityTimeLimit:3000MS     MemoryLimit:0KB     64bitIOFormat:%lld&%lluSubmit StatusDescription  ImmediateDecodability Anencodingofasetofsymbolsissaidtobe immediately decodableifnocode......
  • UVA10237 Bishops
      #include<iostream>#include<cstring>#include<queue>usingnamespacestd;constintN=2e5+2;#defineintlonglongintn,m,f1[50][2000],f2[50][2000];voidsov(){ memset(f1,0,sizeoff1);memset(f2,0,sizeoff2); f1[0][0]=f2......
  • UVA How Many Points of Intersection?
      HowManyPointsofIntersection? a dotsonthetoprowand b dotsonthebottomrow.Wedrawlinesegmentsconnectingeverydotonthetoprowwitheverydotonthebottomrow.Thedotsarearrangedinsuchawaythatthenumberofinternalintersectio......