发布时间：2025-05-22

同余最短路

1. 给定$n$个整数，可以重复取，能拼凑出多少个其他整数
2. 给定$n$个整数，不能拼凑出的最小(最大)整数
3. 至少要多少个数才能拼出模$K$余$p$的数

给定$n$个整数，可以重复取，能拼凑出多少个其他整数

给定$x,y,z,h$对于$k \in [1,h]$有多少个$k$满足$ax+by+cz =k(0 \leq a,b,c,1 \leq x,y,z \leq 10^5,h \leq 2^{63}-1)$

选取$\min(x,y,z)$，假设$x \leq y \leq z$

那么加边add(i,(i+y)%x,y),add(i,(i+z)%x,x)

那么找到了模$x$下的最小整数解，对于任意的答案$ans$，$ans+kx$也能做到，因此求$\sum_{i=0}^{x-1}\lfloor \frac{h-d_i}{x}\rfloor+1$

void solve(){
	int h,x,y,z;
	cin>>h>>x>>y>>z;
	h--;//h-1,从0开始
	if(y<x)swap(x,y);
	if(z<x)swap(x,z);
	vector<int> dis(x,LLONG_MAX);
	priority_queue<PII,vector<PII>,greater<>> pq;
	pq.push({0,0});
	dis[0]=0;
	while(!pq.empty()){
		auto [d,u]=pq.top();
		pq.pop();
		if(d>dis[u])continue;
		for(auto val:{y,z}){
			int v=(u+val)%x;
			if(dis[v]>d+val){
				dis[v]=d+val;
				pq.push({dis[v],v});
			}
		}
	}
	int ans=0;
	for(int i=0;i<x;i++){
		if(dis[i]<=h)ans+=(h-dis[i])/x+1;
	}
	cout<<ans<<"\n";
}

给定$n$个整数，不能拼凑出的最大整数

记A序列最小值为$x$

答案是$\max(dis_i-x)$

• 特判：如果存在$1$，那么任意数都能被表达；如果gcd>1，那么有无限个不能被表达的数，不存在最大值

void solve(){
	int n,m;
	cin>>n>>m;
	vector<int> a;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		for(int j=0;j<=m&&x-j>=1;j++)a.push_back(x-j);
	}
	int g=0;
	for(auto x:a){
		if(x==1){
			cout<<"-1\n";
			return;
		}
		g=__gcd(g,x);
	}
	if(g>1){
		cout<<"-1\n";
		return;
	}
	ranges::sort(a);
	vector<int> dis(a[0],INF);
	priority_queue<PII,vector<PII>,greater<PII>> pq;
	pq.push({0,a[0]});
	dis[0]=0;
	while(!pq.empty()){
		auto [d,u]=pq.top();
		pq.pop();
		if(d>dis[u])continue;
		for(int i=1;i<a.size();i++){
			int v=(u+a[i])%a[0];
			if(dis[v]>d+a[i]){
				dis[v]=d+a[i];
				pq.push({dis[v],v});
			}
		}
	}
	int ans=-1;
	for(int i=0;i<a[0];i++)ans=max(ans,dis[i]-a[0]);
	cout<<ans<<"\n";
}

背包问题，容量$10^{11}$

假设基准值为$m$，一个物品为$v_i$，那么只会存在$gcd(v_i,m)$个环，转两圈的方法就可以更新所有答案

选择单位体积价值最大的作为基准点

$f_{(p+v_i) \mod m}=f_p+c_i-\lfloor \frac{p+v_i}{m}\rfloor w$

$f_p+\frac{V}{m}*w$就是答案

复杂度为$O(nm)$

void solve(){
	int n,q;
	cin>>n>>q;
	vector<int> v(n+1),c(n+1);// 容量，价值
	int m=-1,w=-1;
	for(int i=1;i<=n;i++){
		cin>>v[i]>>c[i];
		if(m==-1||w*v[i]<c[i]*m){
			m=v[i];
			w=c[i];
		}
	}
	vector<int> dp(m,-INF);
	dp[0]=0;
	for(int i=1;i<=n;i++){
		for(int j=0,lim=__gcd(v[i],m);j<lim;j++){
			for(int p=j,_=0;_<2;_+=p==j){
				if(dp[p]!=-INF)dp[(p+v[i])%m]=max(dp[(p+v[i])%m],dp[p]+c[i]-(p+v[i])/m*w);
				p=(p+v[i])%m;
			}
		}
	}
	while(q--){
		int V;
		cin>>V;
		int x=V%m;
		if(dp[x]==-INF) cout<<"-1\n";
		else cout<<dp[x]+V/m*w<<"\n";
	}
}