题目描述

难度分:$1500$

输入$n(1 \leq n \leq 1000)$。

$A$和$B$玩一个猜数字游戏。$A$心中想一个在$[1,n]$中的数字$x$。$B$去猜$x$是多少。

猜测方法：$B$一次性询问所有要询问的数，$A$对于每个询问的数$y$，回答$x$能否被$y$整除。

$B$至少要询问多少个数，才能保证可以猜出数字$x$？输出询问的数字个数，以及具体询问了哪些数。

注意：$B$知道$n$是多少。

输入样例$1$

4

输出样例$1$

3
2 4 3

输入样例$2$

6

输出样例$2$

4
2 4 3 5 

算法

递推

挺有意思的一道题，在做的时候不太确定解法对不对，如果是比赛的话最好是自己多对拍几个$n$，这题光凭样例还是挺容易WA的。

1. 当$n=1$时，直接输出$0$。
2. 当$n=2$时，只需要询问能不能被$2$整除。
3. 当$n=3$时，只需要询问能不能被$2$整除，能不能被$3$整除，两个数足矣。
4. 否则先将$2$和$3$加入答案集合$ans$，然后从$4$开始递推。对于某个数$num$，枚举它在区间$[2,n)$里的约数$d$，只要$d \lt \frac{num}{d}$且两者都能被$ans$里面的数表示出来（可以用一个$dp$数组标记所有能被表示出来的数），并且$d$不是$\frac{num}{d}$的因子，那当前的$num$就不用加入$ans$了。否则就说明当前掌握的所有因子不能唯一确定出$num$，需要加入$num$这个数，才能把$num$猜出来。

递推完$n$后，得到的$ans$数组就是我们要求的答案，相继输出$ans$的大小和其中所有的元素即可。

复杂度分析

时间复杂度

遍历$num \in [4,n]$时间复杂度为$O(n)$。对于每个$num$，需要遍历它的约数，从$2$枚举到$num-1$也是$O(n)$的时间复杂度。因此，整个算法的时间复杂度为$O(n^2)$。

空间复杂度

空间消耗主要在于标记数组$dp$，它是线性的，额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 1001;
int n;
bool dp[N];

int main() {
    scanf("%d", &n);
    if(n == 1) {
        puts("0");
    }else if(n == 2) {
        puts("1\n2");
    }else if(n == 3) {
        puts("2\n2 3");
    }else {
        memset(dp, 0, sizeof dp);
        dp[1] = dp[2] = dp[3] = true;
        vector<int> ans{2, 3};
        for(int num = 4; num <= n; num++) {
            for(int d = 2; d < num; d++) {
                if(num % d == 0 && d < num / d && num / d % d != 0) {
                    dp[num] = dp[num] || (dp[d] && dp[num / d]);
                }
            }
            if(!dp[num]) {
                dp[num] = true;
                ans.push_back(num);
            }
        }
        printf("%d\n", (int)ans.size());
        for(int factor: ans) {
            printf("%d ", factor);
        }
    }
    return 0;
}