当前位置：首页 > news >正文

打卡信奥刷题（3351）用C++实现信奥题 P9560 [SDCPC 2023] Math Problem

news 2026/6/1 19:53:44

P9560 [SDCPC 2023] Math Problem

题目描述

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

选择一个整数x xx满足0 ≤ x < k 0 \leq x < k0≤x<k，将n nn变为k ⋅ n + x k\cdot n+xk⋅n+x。该操作每次花费a aa枚金币。每次选择的整数x xx可以不同。
将n nn变为⌊ n k ⌋ \lfloor \frac{n}{k} \rfloor⌊kn⌋。该操作每次花费b bb枚金币。其中⌊ n k ⌋ \lfloor \frac{n}{k} \rfloor⌊kn⌋表示小于等于n k \frac{n}{k}kn的最大整数。

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

输入格式

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

第一行输入五个正整数n nn，k kk，m mm，a aa，b bb（1 ≤ n ≤ 10 18 1\leq n\leq 10^{18}1≤n≤1018，1 ≤ k , m , a , b ≤ 10 9 1\leq k, m, a, b\leq 10^91≤k,m,a,b≤109）。

输出格式

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

【样例解释】

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

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

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

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

输入输出样例 #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>usingnamespacestd;intt,k,m,a,b;longlongp[70],cnt,n;intmain(){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;}longlongans=1e18;for(inti=1;i<=cnt;i++){if(k==1)//k=1要特判{if(p[i]%m==0)ans=min(ans,1ll*(i-1)*b);continue;}intl=p[i],r=p[i];longlongsum=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";elsecout<<-1<<"\n";}return0;}