10.16 考试解题报告

T1

#题目描述：

对于给定的一个正整数n，判断n是否能分成若干个正整数之和（可以重复），
其中每个正整数都能表示成两个质数乘积。

#输入描述：

第一行一个正整数 q，表示询问组数。
接下来 q 行，每行一个正整数 n，表示询问。

#输出描述：

q 行，每行一个正整数，为 0 或 1。0 表示不能，1 表示能。

#样例输入：

5
1
4
5
21
25

#样例输出：

0
1
0
1
1

#数据范围:

\(30\%\)的数据满足：\(q\leq20, n\leq20\)
\(60\%\)的数据满足：\(q\leq10000, n\leq5000\)
\(100\%\)的数据满足：\(q\leq10^5, n \leq 10^{18}\)

解题思路：

看到这个奇葩的数据范围，我先看到了\(100\%\)的\(n \leq 10^{18}\)
然后我就不知道怎么想的，写了一个不知道能不能跑过60分的完全背包？

code:

#include <bits/stdc++.h>
#define N 5010
#define ll long long
#define M 1010
#define _ 0

using namespace std;
map<int, int> mp; bool vis[N], b[N];
int q, m, mx, mi = 99999999, cnt, tot;
int po[10000100], f[N], qust[N << 1], prime[N];

int read() {
    int s = 0, f = 0;
    char ch = getchar();
    while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
    return f ? -s : s;
}

void erlur(int s) {
    for (int i = 2; i <= s; i++) {
        if (!vis[i]) prime[++cnt] = i;
        for (int j = 1; j <= cnt; j++) {
            if (i * prime[j] > s) break;
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) break;
        }
    }
}

int main() {
    freopen("a.in", "r", stdin);
//  freopen("a.out", "w", stdout);
    q = read();
    for (int i = 1; i <= q; i++) {
        qust[i] = read();
        mx = max(mx, qust[i]);
    }
    erlur(mx);
    for (int i = 1; i <= cnt; i++)
        for (int j = 1; j <= cnt; j++) {
            int an = prime[i] * prime[j];
            if (!mp[an] && an <= mx)
                mp[an] = 1, po[++tot] = an, mi = min(mi, an);
        }
    cout << tot << "\n";
    for (int i = 1; i <= q; i++) {
        if (b[qust[i]]) cout << 1 << " ";
        else {
            memset(f, 0, sizeof(f));
            int flag = 0;
            for (int j = 1; j <= tot; j++)
                for (int k = po[j]; k <= qust[i]; k++) {
                    f[k] = max(f[k], f[k - po[j]] + po[j]);
                    if (f[k] == qust[i]) flag = 1;
                }
            if (flag) b[qust[i]] = 1, puts("1");
            else puts("0");
        }
    }
    return 0;
}

在打出来的时候尝试一下\(60\%\)的范围，结果发现自己的程序跑步过去，然后就把前\(1000\)个输了出来，然后发现除了前边的\(1,2,3,5,7,11\)之外所有的数都是1，只有这两个是0.

证明啊

当\(n \leq 20\) 时, 只有\(1,2,3,5,7,11\)无解，其余均有解。
当\(n > 20\) 时, 因为\(n = (n - 4) + 4 = (n-4) + 2 \ast 2\),而\((n-4)\)这个数\(\geq16\), 是一定有解的。
所以,我们证明了对于任意的正整数\(n\),只有\(n = 1,2,3,5,7,11\)时无解，其余均有解。

正解代码：

#include <bits/stdc++.h>
#define N 100010
#define M 1010
#define _ 0

using namespace std;
long long q, n;

int read() {
    int s = 0, f = 0; char ch = getchar();
    while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
    return f ? -s : s;
}

int main() {
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    q = read();
    for (int i = 1; i <= q; i++) {
        n = read();
        if (n == 1 || n == 2 || n == 3 || n == 5  || n == 7 || n == 11) puts("0");
        else puts("1");
    }
    return 0;
}

正整数