欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

【CSP-S膜你考】 A

程序员文章站 2023-11-17 18:49:28
A 题面 对于给定的一个正整数n, 判断n是否能分成若干个正整数之和 (可以重复) , 其中每个正整数都能表示成两个质数乘积。 输入格式 第一行一个正整数 q,表示询问组数。 接下来 q 行,每行一个正整数 n,表示询问。 输出格式 q 行,每行一个正整数,为 0 或 1。0 表示不能,1 表示能。 ......

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;
}