题目解析

我们有一个数字 $N$，由数字 $d$ 重复 $n!$ 次构成。
需要找出所有奇数 $x \in \{1,3,5,7,9\}$ 使得 $x \mid N$。

关键观察

1. 周期性规律

对于固定的 $d$，随着 $n$ 增大，$n!$ 会迅速增长，但数的整除性会趋于稳定。
因为 $N$ 是由 $d$ 重复 $n!$ 次，而 $n!$ 的增长包含越来越小的数字的倍数。

实际上，当 $n \ge 7$ 时，$n!$ 一定能被 $1,2,\dots,7$ 的所有因子整除，从而 $N$ 的整除模式对 $n \ge 7$ 是固定的。
因此我们可以将 $n$ 截断到 $\min(n, 7)$。

2. 暴力验证

因为 $7! = 5040$，所以截断后 $N$ 的长度最多为 $5040$ 位。
我们可以直接构造这个巨大的数（在 C++ 中可能溢出，需要用大整数或模运算），但更简单的方法是：
用字符串重复 $d$，然后转换为大整数（Python 支持大整数，C++ 需要用模运算）。

C++ 中，我们可以用模运算模拟大数取模：
对于每个要判断的奇数 $x$，我们遍历 $N$ 的每一位，维护当前余数 rem = (rem * 10 + digit) % x，最后检查 rem == 0。

算法步骤

1. 读入 $t$。
2. 对每个测试用例：
   • 读入 $n, d$。
   • 令 $n = \min(n, 7)$。
   • 计算 $m = n!$。
   • 构造字符串 $s$，包含 $m$ 个字符 $d$（或直接模拟）。
   • 对每个奇数 $x \in \{1,3,5,7,9\}$：
     • 模拟大数取模，判断 $x$ 是否整除。
     • 如果整除，输出 $x$。
   • 输出换行。

时间复杂度

每个测试用例最多处理 $5040 \times 5 = 25200$ 次运算，$t \le 100$，总运算量约 $2.5 \times 10^6$，完全可行。

C++ 代码实现

#include <bits/stdc++.h>
using namespace std;

// 计算阶乘
int factorial(int n) {
    int res = 1;
    for (int i = 2; i <= n; i++) {
        res *= i;
    }
    return res;
}

// 判断由 m 个数字 d 重复构成的数是否能被 x 整除
bool divisible(int d, int m, int x) {
    int rem = 0;
    for (int i = 0; i < m; i++) {
        rem = (rem * 10 + d) % x;
    }
    return rem == 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        long long n;
        int d;
        cin >> n >> d;

        // 截断 n 到 7
        if (n > 7) n = 7;
        int m = factorial(n);  // m = n!

        for (int x = 1; x <= 9; x += 2) {
            if (divisible(d, m, x)) {
                cout << x << ' ';
            }
        }
        cout << '\n';
    }

    return 0;
}

验证样例

输入：

3
2 6
7 1
8 5

输出：

1 3 
1 3 7 9 
1 3 5 7 9 

与题目输出一致。

补充说明

• 当 $n=2$ 时，$2! = 2$，数字是 $dd$，如 $66$ 能被 $1,3$ 整除，符合输出。
• 当 $n=7$ 时，$7! = 5040$，数字是 $5040$ 个 $1$，能被 $1,3,7,9$ 整除。
• 当 $d=5$ 时，数字末位是 $5$，所以一定能被 $5$ 整除，但算法会正确判断。
• 该解法利用了 $n \ge 7$ 后结果稳定的数学事实，避免了处理超大数。