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

P9560 [SDCPC 2023] Math Problem题目描述给定两个正整数n nn和k kk您可以进行以下两种操作任意次包括零次选择一个整数x xx满足0 ≤ x k 0 \leq x k0≤xk将n nn变为k ⋅ n x k\cdot nxk⋅nx。该操作每次花费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 TT1 ≤ T ≤ 10 5 1\leq T\leq 10^51≤T≤105表示测试数据组数。对于每组测试数据第一行输入五个正整数n nnk kkm mma aab bb1 ≤ n ≤ 10 18 1\leq n\leq 10^{18}1≤n≤10181 ≤ 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 n101n101最优操作如下首先进行一次第二种操作将n nn变为⌊ n 4 ⌋ 25 \lfloor \frac{n}{4} \rfloor25⌊4n​⌋25花费5 55枚金币。接下来进行一次第一种操作选择x 3 x 3x3将n nn变为4 ⋅ n 3 103 4\cdot n31034⋅n3103花费3 33枚金币。接下来进行一次第一种操作选择x 2 x 2x2将n nn变为4 ⋅ n 2 414 4\cdot n24144⋅n2414花费3 33枚金币。此时414 2 × 207 4142 \times 2074142×207满足n nn是m mm的倍数。共花费5 3 3 11 5331153311枚金币。对于第二组样例数据进行两次第二种操作将n nn变为0 00。共花费1 1 2 1 1 2112枚金币。对于第三组样例数据因为n 114 6 × 19 n 114 6 \times 19n1146×19已经是m mm的倍数因此无需进行任何操作。共花费0 00枚金币。输入输出样例 #1输入 #14 101 4 207 3 5 8 3 16 100 1 114 514 19 19 810 1 1 3 1 1输出 #111 2 0 -1C实现#includebits/stdc.husingnamespacestd;intt,k,m,a,b;longlongp[70],cnt,n;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cint;while(t--){cinnkmab;cnt1,p[1]n;while(k!1n!0)//p中记录所有操作二的可能结果{n/k;p[cnt]n;}longlongans1e18;for(inti1;icnt;i){if(k1)//k1要特判{if(p[i]%m0)ansmin(ans,1ll*(i-1)*b);continue;}intlp[i],rp[i];longlongsum1ll*(i-1)*b;while(l/mr/ml%m!0r%m!0){l*k,r*k;rk-1;suma;}ansmin(ans,sum);}if(ans!1e18)coutans\n;elsecout-1\n;}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容