CodeforcesRound#466(Div.2)B.OurTanyaisCryingOutLoud[将n变为1，有两种方式,求最小花费/贪心]

/*
题意：将n变为1，有两种方式①n-1花费a,②如果n能够被k整除，n=n/k,花费b,求最小花费
*/
/*
很显然这是道贪心题，
一个很容易错的地方就是想着优先除二，然后在减一，
因为没有考虑两者的花费，如果b很大的话就错了，所以每次都要判断下，然后注意细节就行了
*/
#include
using namespace std;
#define pb push_back
#define mem(a) memset(a,0,sizeof(a))
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=150;
const int inf=0x3f3f3f3f;
int main()
{
    ll x,n,k,a,b,ans;
    while(~scanf("%lld%lld%lld%lld",&n,&k,&a,&b)){
        ans=0;
        if(k==1) return 0*printf("%lld\n",a*(n-1));  //注意特判k==1的情况，防止死循环
        while(n!=1){
            //n无法整除k
            if(n%k!=0){    //不能整除只能减法(a)，减到整除为止  
                ans+=a*(n%k);
                n-=(n%k);
            }
            if(n//此时只能减法(a)，除法永远用不到，直接求解答案  
                ans+=a*(n-1);
                break;
            }
            //n可以整除k
            ans+=min(b,a*(n-n/k)); //减法(a)和除法(b)取最小花费  
            n/=k; //n可以整除k
        }
        printf("%lld\n",ans);
    }
}
/*
n-n/k*k = n%k
获取距离n最近的k的倍数的方法是:n/k*k = n-n%k
*/