A
題面
對于給定的一個正整數n， 判斷n是否能分成若干個正整數之和 （可以重復） ，
其中每個正整數都能表示成兩個質數乘積，
輸入格式
第一行一個正整數 q，表示詢問組數，
接下來 q 行，每行一個正整數 n，表示詢問，
輸出格式
q 行，每行一個正整數，為 0 或 1，0 表示不能，1 表示能，
樣例
\(\texttt{input\#1}\)
5
1
4
5
21
25
\(\texttt{output\#1}\)
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
題解
4x + 6y 可以湊出大于等于4的全部偶數，又因為4x + 6y 可以拆成x個2 * 2及y個2 * 3相加，所以大于等于4的偶數全部可拆，大于等于13的奇數完全可以表示成大于等于4的偶數加9，大于等于4的偶數全部可拆，9也可拆，所以大于等于13的奇數也可拆，小于等于12的數中4,6,8,9,10,12是可拆的，0,1,2,3,5,7,11是不可拆的，所以大于等于12的全可拆，小于12的只有4,6,8,9,10可拆，
\(Code\)
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
typedef long long ll;
ll q,n;
inline void read(ll &T) {
ll x=0;bool f=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
T=f?-x:x;
}
int main() {
read(q);
while(q--) {
read(n);
if(n>=12) puts("1");
else {
if(n==4||n==6||n==8||n==9||n==10) puts("1");
else puts("0");
}
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/96310.html
標籤：C++
上一篇：C++和c語言的區別
下一篇：string字串成員函式