P9560 [SDCPC 2023] Math Problem

题目描述

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

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

给定正整数 $m$，求将 $n$ 变为 $m$ 的倍数最少需要花费几枚金币。请注意：$0$ 是任何正整数的倍数。

输入格式

有多组测试数据。第一行输入一个整数 $T$（$1\le T\le 10^5$）表示测试数据组数。对于每组测试数据：

第一行输入五个正整数 $n$，$k$，$m$，$a$，$b$（$1\le n\le 10^{18}$，$1\le k,m,a,b\le 10^9$）。

输出格式

每组数据输出一行一个整数，代表将 $n$ 变为 $m$ 的倍数最少需要花费几枚金币。如果无法完成该目标，输出 $-1$。

【样例解释】

对于第一组样例数据，一开始 $n=101$，最优操作如下：

• 首先进行一次第二种操作，将 $n$ 变为 $\lfloor \frac{n}{4}\rfloor =25$，花费 $5$ 枚金币。
• 接下来进行一次第一种操作，选择 $x=3$，将 $n$ 变为 $4\cdot n+3=103$，花费 $3$ 枚金币。
• 接下来进行一次第一种操作，选择 $x=2$，将 $n$ 变为 $4\cdot n+2=414$，花费 $3$ 枚金币。
• 此时 $414=2\times 207$，满足 $n$ 是 $m$ 的倍数。共花费 $5+3+3=11$ 枚金币。

对于第二组样例数据，进行两次第二种操作将 $n$ 变为 $0$。共花费 $1+1=2$ 枚金币。

对于第三组样例数据，因为 $n=114=6\times 19$ 已经是 $m$ 的倍数，因此无需进行任何操作。共花费 $0$ 枚金币。

输入输出样例 #1

输入 #1

4
101 4 207 3 5
8 3 16 100 1
114 514 19 19 810
1 1 3 1 1

输出 #1

11
2
0
-1

C++实现

#include<bits/stdc++.h>
using namespace std;
int t,k,m,a,b;
long long p[70],cnt,n;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>t;
	while(t--)
	{
		cin>>n>>k>>m>>a>>b;
		cnt=1,p[1]=n;
		while(k!=1&&n!=0)//p中记录所有操作二的可能结果
		{
			n/=k;
			p[++cnt]=n;
		}
		long long ans=1e18;
		for(int i=1;i<=cnt;i++)
		{
			if(k==1)//k=1要特判
			{
				if(p[i]%m==0)
					ans=min(ans,1ll*(i-1)*b);
				continue ;
			}
			int l=p[i],r=p[i];
			long long sum=1ll*(i-1)*b;
			while(l/m==r/m&&l%m!=0&&r%m!=0)
			{
				l*=k,r*=k;
				r+=k-1;
				sum+=a;
			}
			ans=min(ans,sum);
		}
		if(ans!=1e18)
		cout<<ans<<"\n";
		else
		cout<<-1<<"\n";
	}
	return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容