同余最短路

同余最短路

同余最短路可以用于解决形如 "给定 \(n\) 个整数，求这 \(n\) 个整数能拼凑出多少的其他的整数（ \(n\) 个整数可以重复选取）" 以及 "给定 \(n\) 个整数，求这 \(n\) 个整数不能拼凑出的最小（最大）的整数"，或者 "至少要拼几次才能拼出模 \(k\) 余 \(p\) 的数 的问题的时候可以使用同余最短路的方法。

同余最短路利用同余来构造一些状态，可以达到优化空间复杂度的目的。
类比差分约束的方法，利用同余构造的这些状态可以看作单源最短路中的点，同余最短路的状态转移通常是这样的： \(f_{i+j}=f_i+j\) ，类似单源最短路中的 \(f_v=f_u+edge(u, v)\) 。

下面来看一下板题
Small Multiple

要求\(K\)的倍数？，不就是$$模K等于0$$

考虑建立\(0\sim {K-1}\)z这些虚点存${\color{Red} 模K余i的数的最小数位和} $

如何转移，发现乘10后数位和不变，那么枚举乘10后加\(1\sim 9\)后这个数模\(K\)是多少不就行了

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n;

int vis[1001000],dp[1001000];

priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;

void dij() {
	memset(dp,0x3f,sizeof(dp));
	for(int i=1;i<=9;i++) {  q.push({i,i%n}),dp[i%n]=min(dp[i%n],i);}
//	cout<<dp[0];
	while(!q.empty()) {
		int k=q.top().second;
		q.pop();
		if(vis[k]) continue;
		vis[k]=1;
		for(int i=0;i<=9;i++) {
			int v=(k*10+i)%n;
			if(dp[v]>i+dp[k]) {
				dp[v]=i+dp[k];
				q.push({dp[v],v});
			}
		}
	}
}



signed main() {
    cin>>n;  
    if(!n) cout<<0<<endl;
	return 0;
}`