The 6th Liaoning Provincial Collegiate Programming Contest-2025-辽宁省赛-B. Be knocked off 被抠的键盘（构造题，我们需要思考的就是，我们有没有办法化繁为简？）（一般这种构造题目，无解情况不会特别多） · znzryb
## 题目大意
**题目描述**
你有一个包含数字 $0$ 到 $9$ 的键盘。给定一个正整数 $m$，你的目标是使用键盘打出一个正整数，使其为 $m$ 的倍数。
但是，键盘上有 $k$ 个**正整数**按键损坏了（数字 $0$ 的按键一定完好，只有 $1$ 到 $9$ 中的部分按键可能损坏）。你只能使用剩下的完好按键来打出这个数字。
**输入格式**
第一行包含一个整数 $T$（$1 \le T \le 5 \times 10^4$），表示测试数据的组数。
对于每组测试数据：
第一行包含两个整数 $m$ 和 $k$（$1 \le m \le 10^7$，$0 \le k \le 9$），表示**目标数字必须是** $m$ **的倍数，且有** $k$ **个按键损坏。**
**用其他剩余按键，敲出 m 的倍数。**
第二行包含 $k$ 个互不相同的整数 $p_i$（$1 \le p_i \le 9$），具体表示哪些数字按键被损坏。
**输出格式**
对于每组测试数据：
如果存在合法的构造方案，请以“连续按下某数字 $a$ 共 $b$ 次”的操作序列形式输出：
第一行输出一个整数 $n$（$1 \le n \le 100$），表示操作的数量。
接下来 $n$ 行，每行输出两个整数 $a$ 和 $b$（$0 \le a \le 9$，$1 \le b \le 10^{18}$），表示按下数字 $a$ 共 $b$ 次。
如果不存在任何合法的方案，仅输出一行 `-1`。
**样例**
```
输入:
2
37 7
2 3 5 6 7 8 9
7 9
1 2 3 4 5 6 7 8 9
输出:
2
1 3
0 1
-1
```
**样例解释**
对于第一组样例，给出的操作为：按下数字 $1$ 共 $3$ 次，然后按下数字 $3$ 共 $1$ 次。这样按出来的正整数是 $1110$。由于 $1110 = 37 \times 30$，它是 $37$ 的倍数，并且只使用了未损坏的按键 $1$ 和 $0$，符合题目要求。
对于第二组样例，数字 $1$ 到 $9$ 的按键全部损坏，唯一能打出的是由数字 $0$ 组成的数（值为 $0$）。但题目要求打出的必须是一个**正整数**，因此无法完成任务，输出 `-1`。
## 思路讲解
::: 欧拉定理的介绍以及证明
这是 **Euler 定理**（欧拉定理）。
内容很简洁：对于任意正整数 $m$ 和整数 $a$，若 $\gcd(a, m) = 1$，则
$$
a^{\varphi(m)} \equiv 1 \pmod{m}
$$
其中 $\varphi(m)$ 是欧拉函数，表示 $1$ 到 $m$ 中与 $m$ 互素的正整数个数。
图中的结论就是把 $a = 10$ 代入：因为已经去掉了 $m$ 中 $2$ 和 $5$ 的因子，保证了 $\gcd(10, m) = 1$，所以直接套用 Euler 定理得到 $10^{\varphi(m)} \equiv 1 \pmod{m}$。
**直觉上为什么成立**：考虑模 $m$ 的缩系（即 $1$ 到 $m$ 中所有与 $m$ 互素的数构成的集合 $S$，共 $\varphi(m)$ 个元素）。当 $\gcd(a, m) = 1$ 时，把 $S$ 中每个元素都乘以 $a$，得到的集合模 $m$ 后恰好还是 $S$（因为乘以 $a$ 是模 $m$ 缩系上的一个双射）。于是把所有元素的乘积写出来：
$$
\prod_{x \in S} (ax) \equiv \prod_{x \in S} x \pmod{m}
$$
左边提出 $a$：
$$
a^{\varphi(m)} \times \prod_{x \in S} x \equiv \prod_{x \in S} x \pmod{m}
$$
因为 $\prod_{x \in S} x$ 与 $m$ 互素（$S$ 中每个元素都与 $m$ 互素）（**说白了，只要是除数和 m 互素，就有逆元，就可以除**），可以两边消掉，就得到 $a^{\varphi(m)} \equiv 1 \pmod{m}$。
它的特殊情况是 **Fermat 小定理**：当 $m = p$ 为素数时，$\varphi(p) = p - 1$，即 $a^{p-1} \equiv 1 \pmod{p}$。
:::
呃，首先我们还是一步一步来吧，就是首先，我们可以想到，**就是 m 当中的这个因数还是越少越好嘛，想办法先消掉一些**。
下面这一步也是比较自然的，**因为注意到，0 是永远都在的**。
我们可以把这个 m 当中的因数 2,5 给除掉（因为如果原数字不满足，就加 0 即可），得到的新 m 和这个 10 互质（反正应该就是想办法让原数和 10 互质，可以通过不断除以 10，记录一下除 10 的这个个数，最后 +0 即可）。
然后，就可以想到欧拉定理（**其实我们的构造目标就是一个同余式，我们得到的任何东西，也要想办法化为同余式**）：
这是 **Euler 定理**（欧拉定理）。
对于任意正整数 $m$ 和整数 $a$，若 $\gcd(a, m) = 1$，则
$$
a^{\varphi(m)} \equiv 1 \pmod{m}
$$
不难得出如下结论：
我们现在是构出来了，但是万一 9 被扣了我们不就炸了？
我们发现，只要我们能够勾出来一个全 1 的，我们能够非常自然的勾出全 d 的。
这个最后一步，也挺难的，反正我确实不大能够推出来。使用了变量直接代换的这个技巧，把一个 9 带到了这个整除符号的两边。
```cpp
ll cnt2=0;
while (M%2==0) {
M/=2;
cnt2++;
}
ll cnt5=0;
while (M%5==0) {
M/=5;
cnt5++;
}
ll phi=euler_phi(M);
ll cnt0=max(cnt2,cnt5);
if (cnt0==0) {
cout<<1<<"\n";
}else {
cout<<2<<"\n";
}
cout<<*keys.rbegin()<<" "<<9*phi<<"\n";
if (cnt0!=0) {
cout<<0<<" "<<cnt0<<"\n";
}
```
## AC代码
AC
[https://codeforces.com/gym/106380/submission/366492238](https://codeforces.com/gym/106380/submission/366492238)
::: 源代码
```cpp
/**
* Problem: B. Be knocked off
* Contest: The 6th Liaoning Provincial Collegiate Programming Contest
* Judge: Codeforces
* URL: https://codeforces.com/gym/106380/problem/B
* Created: 2026-03-13 10:57:19
* Author: Gospel_rock
* My blog: https://znzryb.com/
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
/*
*
*/
long long euler_phi(long long n) {
long long res = n;
// p 从 2 开始，逐个递增，试到 sqrt(n) 为止
for (long long p = 2; p * p <= n; p++) {
// 如果 p 能整除 n，那么 p 一定是质数。
// 为什么？因为如果 p 是合数，比如 p = 6 = 2 × 3，
// 那么在 p=2 和 p=3 的时候，n 中的 2 和 3 已经被除干净了，
// 此时 n 不可能被 6 整除，所以 n % 6 != 0，这个 if 进不来。
// 因此能进到这个 if 里的 p，一定是质因子。
if (n % p == 0) {
// 发现质因子 p，对 res 乘上 (1 - 1/p) 这个因子
// 即 res = res / p * (p - 1)
res = res / p * (p - 1);
// 把 n 中所有的 p 除干净
// 这样后续更大的 p 的倍数就不可能再整除 n 了
while (n % p == 0) n /= p;
}
}
// 循环结束后，如果 n > 1，说明 n 还剩一个大于 sqrt(原始n) 的质因子
// （一个数最多只有一个大于 sqrt 的质因子）
if (n > 1) {
res = res / n * (n - 1);
}
return res;
}
void Solve() {
ll M,N;
cin >> M >> N;
set<ll> keys={0,1,2,3,4,5,6,7,8,9};
for (int i=1;i<=N;++i) {
ll a;
cin>>a;
keys.erase(a);
}
if (SZ(keys)==1) {
cout<<-1<<"\n";
return;
}
ll cnt2=0;
while (M%2==0) {
M/=2;
cnt2++;
}
ll cnt5=0;
while (M%5==0) {
M/=5;
cnt5++;
}
ll phi=euler_phi(M);
ll cnt0=max(cnt2,cnt5);
if (cnt0==0) {
cout<<1<<"\n";
}else {
cout<<2<<"\n";
}
cout<<*keys.rbegin()<<" "<<9*phi<<"\n";
if (cnt0!=0) {
cout<<0<<" "<<cnt0<<"\n";
}
#ifdef LOCAL
#endif
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
cin >> lT;
for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
AC
https://codeforces.com/gym/106380/submission/366492238
*/
```
:::
## 心路历程（WA，TLE，MLE……）$37$$1$$1 \le b \le 10^{18}$