P9560 [SDCPC2023] Math Problem 题解

WhitD · 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;
}