题目描述
给定一个整数 \(K\)。求一个 \(K\) 的正整数倍 \(S\),使得 \(S\) 的数位累加和最小。
- \(2 \le K \le {10}^5\);
- \(K\) 是整数。
分析
一个很妙的思路就是暴力。
考虑什么时候会对答案多 \(1\)。无非就是某一位 \(+1\)。
如果没有变化就是 \(\times 10\)。
我们发现这样做一定可以把所有的情况搞到。
本质上就是一个 01 bfs 求最短路。
代码
时间复杂度 \(\mathcal{O}(k)\)。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <queue>
#define int long long
#define PII pair<int,int>
#define N 100005
using namespace std;
int k,b[N];
deque<PII> q;
bool vis[N];
signed main(){cin >> k;q.push_back({1,1});while(!q.empty()) {auto t = q.front();q.pop_front();if (vis[t.first]) continue;vis[t.first] = 1; if (t.first == 0) return cout << t.second,0;if (t.first % 10 < 9) q.push_back({t.first + 1,t.second + 1});q.push_front({t.first * 10 % k,t.second});}return 0;
}