模拟赛题讲解[5]

来自 Roundgod 2022-07-26 noi.ac #2678

题目描述：

对于任意非负整数 \(x\) 和 \(m(2\le m\le 10)\) ，定义 \(f_m(x)\) 为 \(x\) 在 \(m\) 进制下的各位数字之和。给定两个整数 \(k\) 和 \(m\) 。你需要计算在所有满足是 \(k\) 倍数的正数 \(x\) 中,最小的 \(f_m(x)\) 值是多少。

输入格式：

输入第一行包含两个整数 \(k,m(2\le m\le 10)\) 。

输出格式：

在一行中输出一个整数，表示答案。

输入1：

5 10

输出1：

1

输入2：

79992 10

输出2：

36

输入3：

4 5

输出3：

4

数据范围：

对于 \(30\%\) 的数据，\(1\le k\le 100\)

对于 \(100\%\) 的数据，\(1\le k\le 10^6\)

题解：

尝试以最小的花费构造一个数使得其是 \(k\) 的倍数

如果我们把这个构造的过程放在模 \(k\) 的意义下

问题就转化为了，如何以最小的花费构造一个 \(0\)

设 \(d_x,~x \in [0,k)\) 表示构造一个模 \(k\) 意义下为 \(x\) 的数的最小花费

然后尝试转移？

对于构造的数，我们可以乘 \(m\) ，也可以加 \(1\)

前者对应的花费为 \(0\) ，后者对应的花费为 \(1\)

为什么只加 \(1\) 呢？因为加 \(2\) 等价于两次加 \(1\)

于是，这个题就转化为了同余最短路

然后就是同余最短路，甚至不用 \(\text{Dijkstra}\) ，直接01bfs就好了

考场直接打暴力骗分，至今不是很理解同余最短路，有待补充

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
#include <queue>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e6+15)

int k,m,d[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> k >> m;
    for(int i=0; i<k; i++) d[i]=INF;
    d[1]=1; deque<int> q;
    q.push_back(1);
    while(!q.empty())
    {
        int u=q.front(); q.pop_front();
        if(!u){return cout << d[0] << '\n',0;}
        int v=u*m%k; if(d[v]>d[u]){d[v]=d[u]; q.push_front(v);}
        v=(u+1)%k; if(d[v]>d[u]+1){d[v]=d[u]+1; q.push_back(v);}
    }
    cout << d[0] << '\n';
    return 0;
}