POJ2739 Sum of Consecutive Prime Numbers&&Acwing4938 连续质数之和

方法：单调队列

为什么是单调队列？因为这里让我们求连续的质数和，我们可以利用欧拉筛来维护质数，再利用单调队列来维护连续的质数。

代码（ POJ 不支持 C++ 11 差评）：

#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cctype>
namespace FastIo{
	#define gc getchar()
	#define pc(ch) putchar(ch) 
    struct QIO{
    	char ch;
    	int st[40];
    	template<class T>inline void read(T &x){
    		x=0,ch=gc;
    		while(!isdigit(ch))ch=gc;
    		while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=gc;}
		}
		bool pd;
		template<class T>inline void write(T a){
			do{st[++st[0]]=a%10;a/=10;}while(a);
			while(st[0])pc(st[st[0]--]^48);
			pc('\n');
		}
	}qrw;
}
using namespace FastIo;
#define NUMBER1 10000
#define P(A) A=-~A
#define fione(i,a,b) for(register int i=a;i<=b;P(i))
int prime[NUMBER1+5],cnt(0),head,tail,sum;
bool st[NUMBER1+5];
inline void PRIME(){
    st[1]=true;
    fione(i,2,NUMBER1){
        if(!st[i])prime[++cnt]=i;
        for(register int j(1);prime[j]*i<=NUMBER1&&j<=cnt;P(j)){
            st[prime[j]*i]=true;
            if(!i%prime[j])break;
        }
    }
}
signed main(){
    PRIME();
    int n,ans;
    bool pd;
    while(1){
        qrw.read(n);
        if(!n)break;
        head=1,tail=0,sum=0,ans=0;
        fione(i,1,cnt){
            while(head<=tail&&sum>n)sum-=prime[head],P(head);
            if(sum==n)P(ans);
            tail=i,sum+=prime[i];
        }
        while(head<=tail&&sum>n)sum-=prime[head],P(head);
        if(sum==n)P(ans);
        qrw.write(ans);
    }
    exit(0);
    return 0;
}

这是我在 Acwing 提交的代码：

#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cctype>
typedef long long LL;
typedef unsigned long long ULL;
namespace FastIo{
    typedef __uint128_t ULLL;
    static char buf[100000],*p1=buf,*p2=buf,fw[100000],*pw=fw;
    #define gc p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++
    inline void pc(const char &ch){
    	if(pw-fw==100000)fwrite(fw,1,100000,stdout),pw=fw;
    	*pw++=ch;
	}
    #define fsh fwrite(fw,1,pw-fw,stdout),pw=fw
	struct FastMod{
        FastMod(ULL b):b(b),m(ULL((ULLL(1)<<64)/b)){}
        ULL reduce(ULL a){
            ULL q=(ULL)((ULLL(m)*a)>>64);
            ULL r=a-q*b;
            return r>=b?r-b:r;
        }
        ULL b,m;
    }HPOP(10);
    struct QIO{
    	char ch;
    	int st[40];
    	template<class T>inline void read(T &x){
    		x=0,ch=gc;
    		while(!isdigit(ch))ch=gc;
    		while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=gc;}
		}
		bool pd;
		template<class T>inline void write(T a){
			do{st[++st[0]]=HPOP.reduce(a);a/=10;}while(a);
			while(st[0])pc(st[st[0]--]^48);
			pc('\n');
		}
	}qrw;
}
using namespace FastIo;
#define NUMBER1 10000
#define P(A) A=-~A
#define fione(i,a,b) for(register int i=a;i<=b;P(i))
int prime[NUMBER1+5],cnt(0),head,tail,sum;//prime数组维护质数
bool st[NUMBER1+5];
inline void PRIME(){//维护欧拉筛
    st[1]=true;
    fione(i,2,NUMBER1){
        if(!st[i])prime[++cnt]=i;
        for(register int j(1);prime[j]*i<=NUMBER1&&j<=cnt;P(j)){
            st[prime[j]*i]=true;
            if(!i%prime[j])break;
        }
    }
}
signed main(){
    PRIME();
    int n,ans;
    bool pd;
    while(1){
        qrw.read(n);
        if(!n)break;
        head=1,tail=0,sum=0,ans=0;
        fione(i,1,cnt){
            while(head<=tail&&sum>n)sum-=prime[head],P(head);
            if(sum==n)P(ans);
            tail=i,sum+=prime[i];
        }
        while(head<=tail&&sum>n)sum-=prime[head],P(head);
        if(sum==n)P(ans);
        qrw.write(ans);
    }
	fsh;
    exit(0);
    return 0;
}