第4题：质数

先讲一下80分的作法，尺取 ```cpp #include <bits/stdc++.h> using namespace std; bool a[1000010]; int x[1000100]; int main(){ int T; cin>>T; while(T--){ int n; cin>>n; memset(a,1,sizeof(a)); for(int i=2;i*i<=n;i++) if(a[i]) for(int j=i*i;j<=n;j+=i)a[j]=0; int s=0; for(int i=2;i<=n;i++) if(a[i])x[++s]=i; int sum=0,ans=0,ai=0; for(int i=1;i<=s;i++){ sum+=x[i]; while(sum>n)sum-=x[ai],ai++; if(sum==n)ans++; }cout<<ans<<endl; } return 0; } ``` 这种作法时间复制度是很高的，80分，其实重要的不是ai，而是数据组数n，n<=10^6 于是我开始了打表 10^5 打了几分钟，可是  好尴尬呀！ 显然是RP不行，估计省赛都用光了。 更好的做法10^6比10^5大了好多，所以可以用类似于记忆化的东西来优化，再加上快读，快出 ```cpp #include <bits/stdc++.h> using namespace std; bool a[1000010]; int x[1000100],b[1000010]; inline void write(int x){ if(x>9)write(x/10); putchar(x%10+'0'); } inline int read(){ register int x=0,f=1; register char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f*=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return x*f; } int main(){ memset(b,-1,sizeof(b)); int T; T=read(); while(T--){ int n=read(); if(b[n]!=-1){ write(b[n]); putchar('\n'); }else{ memset(a,1,sizeof(a)); for(int i=2;i*i<=n;i++) if(a[i]) for(int j=i*i;j<=n;j+=i)a[j]=0; int s=0; for(int i=2;i<=n;i++) if(a[i])x[++s]=i; int sum=0,ans=0,ai=0; for(int i=1;i<=s;i++){ sum+=x[i]; while(sum>n)sum-=x[ai],ai++; if(sum==n)ans++; }b[n]=ans; write(b[n]); putchar('\n'); } } return 0; } ``` 哇，速度真是快了不是，不过还是80分。 我们还可以将素数表和装素数的数组，放在外面完成，避免重复，浪费时间。 ```cpp #include <bits/stdc++.h> using namespace std; bool a[1000010]; int x[1000100],b[1000010]; inline void write(int x){ if(x>9)write(x/10); putchar(x%10+'0'); } inline int read(){ register int x=0,f=1; register char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f*=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return x*f; } int main(){ int s=0; memset(b,-1,sizeof(b)); int T; T=read(); for(int i=2;i*i<=100000;i++) if(!a[i]) for(int j=i*i;j<=100000;j+=i)a[j]=1; for(int i=2;i<=100000;i++) if(!a[i])x[++s]=i; while(T--){ int n=read(); if(b[n]!=-1){ write(b[n]); putchar('\n'); }else{ int sum=0,ans=0,ai=0; for(int i=1;i<=s;i++){ sum+=x[i]; while(sum>n)sum-=x[ai],ai++; if(sum==n)ans++; }b[n]=ans; write(b[n]); putchar('\n'); } } return 0; } ``` 但是还是TLE 于是我们干脆把仅剩的一个循环在搞到循环外 ```cpp #include <bits/stdc++.h> using namespace std; bool a[100010]; int x[100100],b[100010]; inline void write(int x){ if(x>9)write(x/10); putchar(x%10+'0'); } inline int read(){ register int x=0,f=1; register char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f*=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return x*f; } int main(){ int s=0; int T; T=read(); for(int i=2;i*i<=100000;i++) if(!a[i]) for(int j=i*i;j<=100000;j+=i)a[j]=1; for(int i=2;i<=100000;i++) if(!a[i]){ s++; x[s]=x[s-1]+i; } for(int i=0;i<s;i++) for(int j=i+1;j<=s;j++){ if(x[j]-x[i]>100000)break; b[x[j]-x[i]]++; } while(T--){ int n=read(); write(b[n]); putchar('\n'); } return 0; } ``` ~~基本很龚胤翔一至~~