题意概述
给定一个键盘，有 \(0,1,\cdots,9\) 的数字按键，其中有 \(k\) 个不可用，保证按键 \(0\) 可用。给出一种构造方案使得按出的数为 \(m\) 的倍数，如果不存在输出 \(-1\)。
\(1\le m \le 10^7\)。
思路
要让按出的数是 \(m\) 的倍数，本质就是凑出 \(m\) 的所有质因数。
可以无限制地在末尾添加 \(0\)，相当于 \(2\) 和 \(5\) 的因子是无限的，为方便讨论，删掉 \(m\) 中所有 \(2\) 和 \(5\) 的因子。
删完之后，\(\gcd(m,10)=1\)，根据欧拉定理，得：
\[10^{\varphi(m)} \equiv 1 \pmod m
\]
即：
\[m \mid \underbrace{99\cdots 9}_{\varphi(m) \text{个}}
\]
将 \(9m\) 带入，得：
\[9m \mid \underbrace{99\cdots 9}_{\varphi(9m) \text{个}}
\]
即：
\[m \mid \underbrace{11\cdots 1}_{\varphi(9m) \text{个}}
\]
因此可以按 \(\varphi(9m)\) 次相同任意按键，最后补上足够多 \(0\) 即可，当只有按键 \(0\) 的时候无解。
考虑到空间限制，可能无法预处理所有欧拉函数值，采取求单个欧拉函数的方法。
时间复杂度 \(\mathcal{O}(T \sqrt{m})\)。
代码
//author:kzssCCC#include <bits/stdc++.h>
using namespace std;
using ll = long long;void solve(){int m,k;cin >> m >> k;vector<bool> use(10,true);for (int i=1;i<=k;i++){int v;cin >> v;use[v] = false;}int v = -1;for (int i=1;i<=9;i++){if (use[i]){v = i;break;}}if (v==-1){cout << -1 << '\n';return;}while (m%5==0){m/=5;}while (m%2==0){m/=2;}auto cal = [&](ll x){ll res = x;for (ll i=2;i*i<=x;i++){if (x%i==0){while (x%i==0){x/=i;}res -= res/i;}}if (x>1){res -= res/x;}return res;};cout << 2 << '\n';cout << v << ' ' << cal(9*m) << '\n';cout << 0 << ' ' << (ll)1e8 << '\n';
}int main(){ios::sync_with_stdio(false);cin.tie(0);int t;cin >> t;while (t--) solve();return 0;
}