之前寫過一篇介紹同余最短路的文章，其實寫的蠻爛得，鴿了這道題好久，今天中午好不容易算是做出來了。

題意

給定一個 \(K\)，求出來 \(V=xk\)(\(x\) 為正整數)，使得這個 \(V\) 的各數位和是最小的。

這個 \(K\) 的級別是 1e5 的。

做法

我們發現直接去具體搞明白到底是哪一個數幾乎是不可能的，我們不排除有一個長到你無法想象的樹中間有一大堆 0 最后還是最優的，所以我們基本上否決的直接得出數的想法了。

那么我們的重心就自然而然轉向維護數位和上了。

我們不難發現一個 \(V\) 的必然的性質是 \(V%K=0\)，而這個 \(K\) 的范圍又是如此的眉清目秀。

為什么不維護所有數呢？我這么想到。

往同余最短路考慮一下。

我們設 \(dis[i]\) 表示 \(%K=i\) 的數字中，數位和最小的數字是多少。

我們選擇從小到大思考，一個數想到一個更大的數，歸根結底有兩種方式。

一個是加一，一個是乘十，其他的都是這個的組合。

所以我們不難列出來約束條件。

$f_i \ge f_{(i+10)\mod K} $

\(f_i +1 \ge f_{(i+1)\mod K}\)

這樣就顯然起來了，按照這個約束連邊就行了，應該都會同余最短路和差分約束吧，到這里就結束了。

代碼↓

#include <bits/stdc++.h>
using namespace std;
const int MN=1e6+116;
struct Node{
	int nxt, to, w;
}node[MN];
int head[MN], tottt;
void insert(int u, int v, int w){
	node[++tottt].to=v;
	node[tottt].w=w;
	node[tottt].nxt=head[u];
	head[u]=tottt; return;
}
int K;
int dis[MN], vis[MN];
void Dijkstra(int s){
	memset(dis,0x3f,sizeof(dis));
	memset(vis,false,sizeof(vis));
	priority_queue <pair<int,int>> q;
	q.push({0,s}); dis[s]=1;
	while(!q.empty()){
		int u=q.top().second; q.pop();
		if(vis[u]) continue; vis[u]=true;
		for(int i=head[u];i;i=node[i].nxt){
			int v=node[i].to, w=node[i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push({-dis[v],v});
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin>>K;
	for(int i=0; i<K; ++i){
		insert(i,(i*10)%K,0);
		insert(i,(i+1)%K,1);
	}
	Dijkstra(1);
	cout<<dis[0]<<'\n';
	return 0;
}