[??记录]AT3621 [ARC084B] Small Multiple
command_block
2021-05-14 07:13:10
**题意** ： 给定整数 $k$。
求 $c\in \rm Z^+$ ，使得 $ck$ 在十进制下的数位和最小，输出这个最小值。
$k\leq 10^5$。
------------
若 $k=2^t$ ，则要配上 $c=5^t$ 得到最优方案 $10^t$。此时 $c\geq 10^{11}$ ，故不能直接枚举 $c$。
考虑我们是如何构造一个数 $m$ 的。
- $m\leftarrow m\times 10$ ：数位和不变。
- $m\leftarrow m+1$ ： 若不进位，数位和加一，否则数位和可能减少。
考虑同余最短路，记 $dis_i$ 表示模 $k=i$ 的数中数位和最小的。
连边 $i\rightarrow 10i\bmod k$ ，边权为 $0$。
连边 $i\rightarrow (i+1)\bmod k$ ，边权为 $1$。
然后跑 $01\ \rm BFS$ 即可，答案是 $dis_0$。
复杂度 $O(k)$。
```cpp
#include<algorithm>
#include<cstdio>
#include<vector>
#define pb push_back
#define MaxN 100500
using namespace std;
const int INF=1000000000;
vector<int> g[MaxN],l[MaxN];
int k,q[MaxN<<1],dis[MaxN];
bool in[MaxN];
int main()
{
scanf("%d",&k);
for (int i=0;i<k;i++){
dis[i]=INF;
g[i].pb((i+1)%k);l[i].pb(1);
g[i].pb(i*10%k);l[i].pb(0);
}
int ql,qr;
dis[1]=1;q[ql=qr=k]=1;
while(ql<=qr){
int u=q[ql++];
if (in[u])continue;
in[u]=1;
for (int i=0,v;i<g[u].size();i++)
if (dis[v=g[u][i]]>dis[u]+l[u][i]){
dis[v]=dis[u]+l[u][i];
if (l[u][i])q[++qr]=v;
else q[--ql]=v;
}
}printf("%d",dis[0]);
return 0;
}
```