专栏文章

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

II_am_kunzi
P14582题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min0wo4a
此快照首次捕获于
2025/12/01 18:45
3 个月前
此快照最后确认于
2025/12/01 18:45
3 个月前
查看原文

P14582 题解

题目思路

首先既然禁用哪些数字是出题人决定的，那么我们就要尽量考虑一种通用的解法，使得可以用尽可能少的数字和步骤得到答案。
观察发现一共有 0∼90 \sim 9 共 1010 个数字，但禁用范围仅为 1∼91 \sim 9 共 99 个数字，即 00 一定不会被禁用。但只有 00 的话只能按出 0 0，虽然是任意正整数的倍数，但 00 不是正整数，所以至少得有一个未被禁用的非零数字，才有可能拼出来答案。
然后还有一个性质，就是只要数字末尾加足够多的 0 0，就可以使答案包括 mm 中所有的 22 和 55 因子。
那么我们就考虑只用一种非零数字和 00 得到 mm 的倍数。根据上一段，这里我们可以先除去 mm 中所有的 22 和 55 因子，当然不除去也可以，因为在数末尾加一个 00 等价于乘 10 10，不会影响答案。
这时假定除去所有 22 和 55 因子后的数为 m′ m'，则一定有 gcd⁡(m′,10)=1 \gcd(m' , 10) = 1。不妨先钦定我们使用的非零数字为 1 1，因为使用 11 得到解法之后，将数整体乘 1∼91 \sim 9 中的某个数字，就可以仅使用某个任意非零数字和 00 得到 m′m' 的倍数。
根据我们小学就学过的知识，并将其形式化书写，如果从低到高第 kk 位的数字为 p p，数共有 nn 位，则这个数就是 ∑i=1kp⋅10k−1 \displaystyle \sum_{i = 1} ^ k p \cdot 10 ^ {k - 1}。在这里我们使用 11 作为非零数字，所以整个数一定是若干个 10k−110 ^ {k - 1} 相加的结果。而我们知道此时有 10φ(m′)≡1(modm)′ 10 ^ {\varphi(m')} \equiv 1 \pmod m'，因为 gcd⁡(m′,10)=1 \gcd(m' , 10) = 1。
那么我们只需要找到 m′m' 个不同的 kk 就可以了，而把上面的式子变形得到 (10φ(m′))x≡1(modm)′ (10 ^ {\varphi(m')}) ^ x \equiv 1 \pmod m'，而 xx 取 0∼m′−10 \sim m' - 1 即可。
这时我们需要输出 m′m' 段 1 1，但每段长度仅为 1 1。我们发现，在最终的数中，相邻两个 11 位置的间隔均为 φ(m′)\varphi(m') 位，而我们可以把每一个 11 变为 φ(m′)\varphi(m') 个 1 1，这样所有的 11 就连起来了，共 φ(m′)⋅m′\varphi(m') \cdot m' 个。
最后输出足量 00 即可。当然实际上不除去 mm 中所有 22 和 55 因子也是正确的，因为此时 11 的数量一定是除掉因子后 11 的数量的倍数。

题目代码

CPP
#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();
    }
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...