ARC084 B Small Multiple 题解

zhln / 2024-09-26 / 原文

原题链接

Description

给定一整数 $k$ , 求一个 $k$ 整数倍的数 $x$ ，使得 $x$ 的数位累加和最小，输出最小的累加和。

Solution

这道题简单但值得一想。

正着枚举每一个 $k$ 整数倍的数 $x$ 肯定会超时，反过来考虑，可以找一个数 $x$ 使其为 $k$ 的倍数，那么对于每个数 $x$ ，均有以下两种操作：

将这个数 $\times 10$ ，对应花费为 $0$
将这个数 $+ 1$ ，对应花费为 $1$

至于说为什么可以转化为这两种操作，主要是一种贪心的思想，我们并不需要考虑 $x$ 的大小，只需要尽量使其花费最小。

实现就很简单了，这里可以使用 $01BFS$ ，将使用花费为 $0$ 操作所得的数插入队首，将花费为 $1$ 的插入队尾，注意跳掉已经找过余数相同数的数。

Code

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
#define MAXN 100100
//#define int long long
int Read()
{
	int x=0,f=1;char c=getchar();
	while(c>'9'||c<'0'){if(c=='-')f=-f;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-48;c=getchar();}
	return x*f;
}
int k,vis[MAXN];
deque<pair<int,int> > q;
int main()
{
	k=Read();
	q.push_front(make_pair(1,1));
	while(!q.empty())
	{
		pair<int,int> qwq=q.front();q.pop_front();
		if(vis[qwq.first]) continue;
		vis[qwq.first]=1;
		if(!qwq.first) return printf("%d",qwq.second),0;
		q.push_front(make_pair(qwq.first*10%k,qwq.second));
		q.push_back(make_pair((qwq.first+1)%k,qwq.second+1));
	}
}