【题目描述】
对于给定的一个正整数n， 判断n是否能分成若干个正整数之和 （可以重复） ，
其中每个正整数都能表示成两个质数乘积。
【输入描述】
第一行一个正整数 q，表示询问组数。
接下来 q 行，每行一个正整数 n，表示询问。
【输出描述】
q 行，每行一个正整数，为 0 或 1。0 表示不能，1 表示能。
【输入样例】
5 1 4 5 21 25
【输出样例】
0 1 0 1 1
【样例解释】
4=2*2
21=6+15=2*3+3*5
25=6+9+10=2*3+3*3+2*5
25=4+4+4+4+9=2*2+2*2+2*2+2*2+3*3
【数据范围】
30%的数据满足：q<=20,n<=20
60%的数据满足：q<=10000,n<=5000
100%的数据满足：q<=10^5,n<=10^18
题意：
q次询问：能否用形如 x = p1 * p2 (p1,p2均为质数且可以相等) 的数相加得到给定的数n。
题解：
当n <= 20 时,只有1,2,3,5,7,11无解，其余均有解。
当n > 20 时,因为n = (n-4) + 4 = (n-4) + 2 * 2,而(n-4)这个数>=16,是一定有解的。
所以,我们证明了对于任意的正整数n,
只有n = 1,2,3,5,7,11时无解，其余均有解。
那么我们只需要在每组数据中判断一下n是否等于1,2,3,5,7,11中的任意一个即可。
复杂度O(q).
明明，，，，
但是我跟个不长脑子的sb似的
想也没想就™暴力开始做
结果，。，，，
60分代码：
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; inline int read() { int s=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-')w=-1; ch=getchar(); } while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar(); return s*w; } int T,n; bool b[10000001],awa[1000001]; int p[1001],cnt; bool prime[5001]; int f[10001]; void isprime() { for(int i=2; i<=1001; i++) { if(prime[i])continue; p[++cnt]=i; for(int j=i+i; j<5001; j+=i) prime[j]=true; } } int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); isprime(); T=read(); int k=0; while(T--) f[++k]=read(); for(int i=1; i<=cnt; i++) for(int j=i; j<=cnt; j++) b[p[i]*p[j]]=true; awa[2]=awa[1]=awa[3]=false; for(int i=4; i<=5001; i++) { if(b[i])awa[i]=true; if(!awa[i])continue; for(int j=4; j<=i; j++) if(awa[j])awa[j+i]=true; } for(int i=1; i<=k; i++) cout<<awa[f[i]]<<"\n"; fclose stdin; fclose stdout; return 0; }
满分代码：
#include<bits/stdc++.h> using namespace std; typedef long long LL; int q; LL n; int rd(){ int re=0,f=1;char c=getchar(); while ((c<'0')||(c>'9')) {if (c=='-') f=-f;c=getchar();} while ((c>='0')&&(c<='9')) {re=re*10+c-'0';c=getchar();} return re*f; } int main(){ freopen("a.in","r",stdin); freopen("a.out","w",stdout); scanf("%d",&q); for (;q>0;--q){ scanf("%lld",&n); if ((n>3ll)&&(n!=5ll)&&(n!=7ll)&&(n!=11ll)) puts("1");else puts("0"); } return 0; }