题解：P14582 [LNCPC 2025] 被抠的键盘

· · 题解

P14582 题解

题目思路

首先既然禁用哪些数字是出题人决定的，那么我们就要尽量考虑一种通用的解法，使得可以用尽可能少的数字和步骤得到答案。

观察发现一共有 0 \sim 9 共 10 个数字，但禁用范围仅为 1 \sim 9 共 9 个数字，即 0 一定不会被禁用。但只有 0 的话只能按出 0，虽然是任意正整数的倍数，但 0 不是正整数，所以至少得有一个未被禁用的非零数字，才有可能拼出来答案。

然后还有一个性质，就是只要数字末尾加足够多的 0，就可以使答案包括 m 中所有的 2 和 5 因子。

那么我们就考虑只用一种非零数字和 0 得到 m 的倍数。根据上一段，这里我们可以先除去 m 中所有的 2 和 5 因子，当然不除去也可以，因为在数末尾加一个 0 等价于乘 10，不会影响答案。

这时假定除去所有 2 和 5 因子后的数为 m'，则一定有 \gcd(m' , 10) = 1。不妨先钦定我们使用的非零数字为 1，因为使用 1 得到解法之后，将数整体乘 1 \sim 9 中的某个数字，就可以仅使用某个任意非零数字和 0 得到 m' 的倍数。

根据我们小学就学过的知识，并将其形式化书写，如果从低到高第 k 位的数字为 p，数共有 n 位，则这个数就是 \displaystyle \sum_{i = 1} ^ k p \cdot 10 ^ {k - 1}。在这里我们使用 1 作为非零数字，所以整个数一定是若干个 10 ^ {k - 1} 相加的结果。而我们知道此时有 10 ^ {\varphi(m')} \equiv 1 \pmod m'，因为 \gcd(m' , 10) = 1。

那么我们只需要找到 m' 个不同的 k 就可以了，而把上面的式子变形得到 (10 ^ {\varphi(m')}) ^ x \equiv 1 \pmod m'，而 x 取 0 \sim m' - 1 即可。

这时我们需要输出 m' 段 1，但每段长度仅为 1。我们发现，在最终的数中，相邻两个 1 位置的间隔均为 \varphi(m') 位，而我们可以把每一个 1 变为 \varphi(m') 个 1，这样所有的 1 就连起来了，共 \varphi(m') \cdot m' 个。

最后输出足量 0 即可。当然实际上不除去 m 中所有 2 和 5 因子也是正确的，因为此时 1 的数量一定是除掉因子后 1 的数量的倍数。

题目代码

#include<iostream>
using namespace std;
bool np[10000005];
int p[5000005];
int phi[10000005];
void calc(int n)
{
    np[1] = 1;
    phi[1] = 1;
    int cntp = 0;
    for(int i = 2 ; i <= n ; i++)
    {
        if(!np[i])
        {
            p[++cntp] = i;
            phi[i] = i - 1;
        }
        for(int j = 1 ; j <= cntp && i * p[j] <= n ; j++)
        {
            np[i * p[j]] = 1;
            phi[i * p[j]] = phi[i] * phi[p[j]];
            if(i % p[j] == 0)
            {
                phi[i * p[j]] = phi[i] * p[j];
                break;
            }
        }
    }
}
void solve()
{
    long long m , k;
    cin >> m >> k;
    bool y[10] = {0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0};
    for(int i = 1 ; i <= k ; i++)
    {
        int x;
        cin >> x;
        y[x] = 1;
    }
    int u = 0;
    for(int i = 1 ; i <= 9 ; i++)
    {
        u = (!y[i] ? i : u);
    }
    if(!u)
    {
        cout << -1 << endl;
        return ;
    }
    cout << 2 << endl << u << ' ' << m * phi[m] << endl << 0 << ' ' << 1000000 << endl;
}
signed main()
{
    calc(1e7);
    int t;
    cin >> t;
    while(t--)
    {
        solve();
    }
}