The 6th Liaoning Provincial Collegiate Programming Contest-2025-辽宁省赛-B. Be knocked off 被抠的键盘（构造题，我们需要思考的就是，我们有没有办法化繁为简？）（一般这种构造题目，无解情况不会特别多）

题目大意

题目描述
你有一个包含数字 $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 带到了这个整除符号的两边。

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

源代码

/**
 * 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

*/

Znzryb's Blog

The 6th Liaoning Provincial Collegiate Programming Contest-2025-辽宁省赛-B. Be knocked off 被抠的键盘（构造题，我们需要思考的就是，我们有没有办法化繁为简？）（一般这种构造题目，无解情况不会特别多）

题目大意

思路讲解

AC代码

心路历程（WA，TLE，MLE……） $37$ $1$ $1 \le b \le 10^{18}$

题目大意

思路讲解

AC代码

心路历程（WA，TLE，MLE……）3737371111≤b≤10181 \le b \le 10^{18}1≤b≤1018

心路历程（WA，TLE，MLE……） $37$ $1$ $1 \le b \le 10^{18}$