当前位置：首页 > news >正文

CF2043b-B. Digits

news 2025/8/3 4:40:28

题目链接

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

题解：

主要是考察分类讨论：

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

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

被7整除，N = d * $\sum 10^{n-1}$ = d * ( $10^{n}$ - 1) / 9，这种情况下要么d能被7整除，要么( $10^{n}$ - 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 * $\sum 10^{n-1}$ = d * ( $10^{n}$ - 1) / 9，这种情况下要么d能被9整除，要么分成两种情况来讨论：一种是d%3 == 0的情况，这种情况要确保( $10^{n}$ - 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的情况，这种情况要确保( $10^{n}$ - 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;
}

查看全文

http://www.lryc.cn/news/513385.html