【题解】变一

题意

给你一个，需要将其变为，每次操作可以选择对减一花费元，或对除以花费元，求将变为的最小花费。

题解

1. 如果当前，只能执行次第一种操作，然后答案加。
2. 如果当前不能被整除，那肯定只能执行第一种操作，次。也就是，然后答案加。
3. 如果能被整除，则判断从到那种操作花费更小，设，判断是和哪个小

复杂度

时间复杂度

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{

    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,k,x,y;
        scanf("%d%d%d%d",&n,&k,&x,&y);
        long long ans=0;
        if(k==1||n<k)
        {
            printf("%lld\n",1ll*(n-1)*x);
            continue;
        }
        while(n>1)
        {
            if(n%k)
            {
                long long t=n%k;
                if(n<k)
                    t--;
                n-=t;
                ans+=x*t;
            }
            else
            {
                if((n-n/k)*x<y)
                    ans+=1ll*(n-n/k)*x;
                else
                    ans+=y;
                n/=k;
            }
        }
        printf("%lld\n",ans);
    }
}