CF2043b-B. Digits

题目链接

题意：给定两个整数n、d，要求找出排列成n!个d之后的数可以被1-9中奇数整除的数

题解：

       主要是考察分类讨论：

               被3整除，当d能被3整除时一定成立或者n >= 3，当n >= 3时n!一定包含因数3

               被5整除，当d能被5整除时成立

               被7整除，N = d *  = d * ( - 1) / 9，这种情况下要么d能被7整除，要么( - 1) / 9能被7整除，我们可以计算10^n mod 7的周期性。通过计算，我们发现10^1 mod 7 = 3 10^2 mod 7 = 2 10^3 mod 7 = 6 10^4 mod 7 = 4 10^5 mod 7 = 5 10^6 mod 7 = 1  因此10^n mod 7的周期性是6为了确保10^n - 1能被7整除 我们需要n是6的倍数。n!为6的倍数n至少为3

                被9整除，N = d *  = d * ( - 1) / 9，这种情况下要么d能被9整除，要么分成两种情况来讨论：一种是d%3 == 0的情况，这种情况要确保( - 1)能被27整除，我们可以计算10^n mod 27的周期性。通过计算，我们发现10^1 mod 27 = 10 10^2 mod 27 = 19 10^3 mod 27 = 1因此10^n mod 27的周期性是3为了确保10^n - 1能被27整除 我们需要n是3的倍数。n!为3的倍数n至少为3；

                另一种情况d % 3 != 0的情况，这种情况要确保( - 1)能被81整除，我们可以计算10^n mod 81的周期性10^n分别mod81得10 19 28 37 46 55 64 73 1，n为9的倍数n!为9的倍数则n至少为6

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

#define fi first 
#define se second
#define ve vector
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for (int i = a; i < b; i++)
#define per(i, a, b) for (int i = a; i >= b; i--)
using i64 = long long;
using pi = pair<i64, i64>;

void solve() {
    int n, d;
    cin >> n >> d;
    ve<int> res;
    res.emplace_back(1);
    if ((d % 3 == 0) || (n >= 3)) {
        res.emplace_back(3);
    }
    if (d == 5) {
        res.emplace_back(5);
    }
    if (d == 7 || n >= 3) {
        res.emplace_back(7);
    }
    if (d == 9) {
        res.emplace_back(9);
    } else if (d % 3 == 0) {
        if (n >= 3) {
            res.emplace_back(9);
        }
    } else if (n >= 6) {
        res.emplace_back(9);
    }
    for (int i = 0; i < res.size(); i++) {
        cout << res[i] << " \n"[i == res.size() - 1];
    }
}

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

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}