同余最短路

同余最短路可以用于解決形如 "給定 \(n\) 個(gè)整數(shù)，求這 \(n\) 個(gè)整數(shù)能拼湊出多少的其他的整數(shù)（ \(n\) 個(gè)整數(shù)可以重復(fù)選取）" 以及 "給定 \(n\) 個(gè)整數(shù)，求這 \(n\) 個(gè)整數(shù)不能拼湊出的最小（最大）的整數(shù)"，或者 "至少要拼幾次才能拼出模 \(k\) 余 \(p\) 的數(shù) 的問題的時(shí)候可以使用同余最短路的方法。

同余最短路利用同余來構(gòu)造一些狀態(tài)，可以達(dá)到優(yōu)化空間復(fù)雜度的目的。
類比差分約束的方法，利用同余構(gòu)造的這些狀態(tài)可以看作單源最短路中的點(diǎn)，同余最短路的狀態(tài)轉(zhuǎn)移通常是這樣的： \(f_{i+j}=f_i+j\) ，類似單源最短路中的 \(f_v=f_u+edge(u, v)\) 。

下面來看一下板題
Small Multiple

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

考慮建立\(0\sim {K-1}\)z這些虛點(diǎn)存${\color{Red} 模K余i的數(shù)的最小數(shù)位和} $

如何轉(zhuǎn)移，發(fā)現(xiàn)乘10后數(shù)位和不變，那么枚舉乘10后加\(1\sim 9\)后這個(gè)數(shù)模\(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});
			}
		}
	}
}

————————————————
P3403

發(fā)現(xiàn)只能往上走，x,y,z，想想和剛才講的有什么聯(lián)系

設(shè)其中最小數(shù)為k，容易發(fā)現(xiàn)只要找到了第一個(gè)%k等于i的數(shù)v，那么v+k，v+2*k...是不是也都可以取到，那么答案呼之欲出了有沒有

注意因?yàn)槭怯鄶?shù)所以每個(gè)點(diǎn)貢獻(xiàn)是\(\frac{n-dis_i}{k}+1\) ，代碼不放了和上面的差不多

————————————————
P2662

首先可以預(yù)處理出來哪些長度可以取到，取最小值s為模數(shù)，直接跑就行

稍微難一點(diǎn)是統(tǒng)計(jì)答案了，如果有不能取到的同余系，那么就無解，否則取$$\underset{i=0}{\overset{s?1}{max}}di{s}_i?s$$
——————————————————
P2371

感覺思路挺一眼的，還是同余系嗎，注意統(tǒng)計(jì)答案時(shí)如何查分就行了，貼一下我的

for(int i=0;i<a[1];i++) {
	ans+=max((r-dis[i]),0ll)/a[1]-max(l-1-dis[i],0ll)/a[1];
	f(r>=dis[i]) ans++;
	if(l-1>=dis[i]) ans--;
}