自动搬运

查看原文

来自洛谷，原作者为

	WhitD %$@oma

搬运于2025-08-24 22:49:35，当前版本为作者最后更新于2023-09-14 20:26:25，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目大意

给定两个正整数 $n$ 和 $k$，您可以进行以下两种操作任意次（包括零次）：

• 选择一个整数 $x$ 满足 $0 \leq x < k$，将 $n$ 变为 $k\times n+x$。该操作每次花费 $a$ 枚金币，每次选择的整数 $x$ 可以不同。
• 将 $n$ 变为 $\lfloor \frac{n}{k} \rfloor$。该操作每次花费 $b$ 枚金币。其中 $\lfloor \frac{n}{k} \rfloor$ 表示小于等于 $\frac{n}{k}$ 的最大整数。

给定正整数 $m$，求将 $n$ 变为 $m$ 的倍数最少需要花费几枚金币。

思路

我们发现，先乘再除对结果是没有影响的（因为操作一加的值小于 $k$，操作二的除法向下取整就把多加的数也除掉了），因此一定是先除再乘。

我们假定当前的数为 $n$，将它进行一次操作一：如果乘完了不加数，它会变成 $n\times k$；如果乘完后加数，最多可以加 $x(x<k)$，也就是 $k-1$，它会变成$n\times k+k-1$。这说明 $n$ 进行完操作一后可以变到的范围是 $[n\times k,n\times k+k-1]$。

于是我们可以先枚举出进行操作二的次数（这个过程是 $\log$ 的），同时进行重复进行操作一直到 $n$ 成为 $m$ 的倍数（根据区间端点来判断是否在区间内），然后计算总代价，全局取 $\min$ 就可以了。

注意特判 $k=1$ 是无解的。

AC 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T;
int main()
{
	cin>>T;
	while(T--)
	{
		ll n,k,m,a,b,ans=114514191981011451;
		cin>>n>>k>>m>>a>>b;
		if(n%m==0)
		{
			cout<<0<<endl;
			continue;
		}
		if(k==1)
		{
			cout<<-1<<endl;
			continue;
		}
		for(ll i=0,d=0;;i++,n/=k,d=i*b)
		{
			if(!n)
			{
				ans=min(ans,b*i);
				break;
			}
			__int128 l=n,r=n;
			while(l%m&&(r/m==l/m))
			{
				r=r*k+k-1;
				l*=k;
				d+=a;
			}
			ans=min(ans,d);
		}
		cout<<ans<<endl;
	}
	return 0;
}