自动搬运

查看原文

来自洛谷，原作者为

	yyandy /oh

搬运于2025-08-24 22:33:07，当前版本为作者最后更新于2022-11-13 15:11:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

关于题目的吐槽

感觉这道题没什么思维含量，但是却处处是细节，处处恶心人。
被某搬题人放在模拟赛里了，赛时根本不想动这道题。
感觉首先是一大堆数据范围，什么 $K,M,T,Q$ 一大堆的，非常容易弄混。
当年的线上赛上没人通过这题大概也是因为这个原因。

题解

题意已经非常简洁了（虽然还是很吓人），这里就不再简化了。
首先仔细读一遍题，大概观察一下，就只有两种操作。
操作一是将一个数变为严格小于它的因数，操作二是在特殊点上原地不动。

不妨先考虑简单的情况，$T=0$，也就是没有特殊点。
考虑到进行操作一最少将原数除以 $2$。
所以操作一的次数肯定是不超过 $O(\log w)$ 的。（其中 $w$ 是值域，下同）
于是我们就可以预处理出 $F_{i,j}$ 表示通过 $j$ 步将 $i$ 变为 $1$ 的最小花费。
这个比较容易计算，每次枚举倍数转移即可。
时间复杂度 $O(w\log w\log n)$。
不理解的可以看一下这一部分代码。

for(int i=1;i<=N;++i){
	int Mlen=Maxlen[i];
	for(int j=(i<<1),c=2;j<=N;j+=i,++c){
		Maxlen[j]=max(Maxlen[j],Mlen+1);
		for(int k=0;k<=Mlen;++k)
			getmin(F[j][k+1],F[i][k]+d[c]);
	}
}

对于每一个 $L_i$，答案就是 $F_{A/B,L_i}$。

解决了这一个简单版本，思考 $T > 0$ 时怎么解决。
对于 $L_i$ 比较小的时候可以简单处理掉，只需要考虑 $L_i$ 较大的时候。
$L_i$ 较大的时候是必须进行若干次操作二的。
有一个很显然的性质就是最多只会在一个特殊点上重复原地不动。
这个通过反证就可以轻易地证明，这里也不再详细描述。
由于只会在一个点原地不动，而 $T$ 又不超过 $50$，我们可以直接枚举这一个点，并取所有情况的最小值。
计算的时候将从起点到特殊点和特殊点到终点这两部分拼接在一起。
实现得优秀一点可以做到 $O(w\log w\log n+QTM+QTlog^2 w)$。
常数不大，卡一卡也许能过？（没试过

但比较容易发现在一个特殊点绕圈再走到终点的花费与步数是一次函数的关系。
然后我们要求的就是这 $T$ 个一次函数在 $x=L_i$ 时的最小值。
这样就可以将 $L_i$ 排序，然后维护一个上凸壳，代替枚举。
时间复杂度 $O(w\log w\log n + QT\log ^2 w + QTM)$。
算一算貌似光预处理部分就要爆了，但实际跑起来非常快，可以通过。

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000000;
const int INF=2.1e9;
int vb[60],vk[60],sz,K,M,d[1000050],F[22][1000008],Maxlen[1000050],T,Q,L[1050],V[10200];
bool canvis[55];
struct D {
	int X,C;
} p[55];
int calc[55][22];
inline double slope(int p1,int p2) {
	return (vb[p2]-vb[p1])*1./(vk[p1]-vk[p2]);
}
inline void insert(int K,int B) {
	while(sz&&vk[sz]==K)if(vb[sz]>B)sz--;
		else return;
	vb[sz+1]=B;
	vk[sz+1]=K;
	while(sz>1&&slope(sz,sz-1)>slope(sz,sz+1))swap(vk[sz],vk[sz+1]),swap(vb[sz],vb[sz+1]),sz--;
	sz++;
}
inline ll solve(int x,int y) {
	if(y%x!=0)return -M;
	memset(canvis,0,sizeof(canvis));
	int c=y/x;
	ll sum=0;
	sz=0;
	for(int i=1; i<=T; ++i)
		if(y%p[i].X==0&&p[i].X%x==0) {
			canvis[i]=1;
			int c1=y/p[i].X,c2=p[i].X/x,Min=1e9;
			for(int len1=0; len1<=Maxlen[c1]; ++len1)
				for(int len2=0; len2<=Maxlen[c2]&&len1+len2<=20; ++len2)
					calc[i][len1+len2]=min(calc[i][len1+len2],F[len1][c1]+F[len2][c2]-(len1+len2)*p[i].C);
			for(int j=1; j<=20; ++j)
				calc[i][j]=min(calc[i][j],calc[i][j-1]);
			Min=calc[i][20];
			insert(p[i].C,Min);
		}
	for(int i=1,k=0,v,ans=0; i<=M; ++i) {
		v=L[i];
		if(v<=20) {
			ans=F[v][c];
			for(int j=1; j<=T; ++j)
				if(canvis[j])
					ans=min(ans,calc[j][v]+v*p[j].C);
			if(ans>1e9)ans=-1;
		}
		else {
			if(!sz)ans=-1;
			else {
				while(k<sz&&slope(k,k+1)<=L[i])++k;
				ans=vk[k]*L[i]+vb[k];
			}
		}
		sum+=ans;
	}
	for(int i=1; i<=T; ++i)
		if(canvis[i])
			memset(calc[i],63,sizeof(calc[i]));
	return sum;
}
bitset<1000010> B1,B2;
void init() {
	memset(F,63,sizeof(F));
	Maxlen[0]=0;
	F[0][1]=0;
	memset(calc,63,sizeof(calc));
	for(int i=1; i<=N; ++i) {
		for(int j=i; j<=N; j+=i)
			d[j]++;
		d[i]=V[d[i]];
	}
	int tot=0,ccc=0;
	for(int i=2; i<=N; ++i)F[1][i]=d[i],Maxlen[i]=1;
	B1.set();
	for(int c=1; c<20; ++c) {
		int *D1=F[c],*D2=F[c+1];
		for(int i=B1._Find_next(0); i<=N; i=B1._Find_next(i)) {
			for(int j=(i<<1),c=2,C=D1[i]; j<=N; j+=i,++c)
				D2[j]=min(D2[j],C+d[c]),B2[j]=1,tot++;
			Maxlen[i]=c;
		}
		B1=B2;
		B2.reset();
	}
}
inline bool cmp(D x,D y) {
	return x.C>y.C;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>K;
	for(int i=1; i<=K; ++i)
		cin>>V[i];
	init();
	cin>>M;
	for(int i=1; i<=M; ++i)
		cin>>L[i];
	sort(L+1,L+M+1);
	cin>>T;
	for(int i=1; i<=T; ++i)
		cin>>p[i].X>>p[i].C;
	sort(p+1,p+T+1,cmp);
	cin>>Q;
	while(Q--) {
		int x,y;
		cin>>x>>y;
		cout<<solve(y,x)<<'\n';
	}
}

官方题解在上面的基础上更进了一步。
主要是利用将数分解为 $p_1^{k_1}\times p_2^{k_2} \times\cdots\times p_t^{k_t}$ 这种形式后。
只要任意两数 $k_1,k_2,\cdots,k_t$ 构成的集合是相同的，那这两数的答案一定是相同的。
由于可能的集合个数非常的少，只有不到 $300$ 个，所以可以枚举集合算答案。
不过实际表现上看并没有比我上面的做法快，但码量却大了许多。
如果感兴趣官方题解的做法，请看这。