14257: 【原4257】复仇

题目

题目描述

author: Guo Linsong 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4257

Description

当你看到这道题时，相信你已经完成了第一次小作业的绝大多数题目。这些题目，可能迫使你爆肝到深夜，可能侵吞了你许多娱乐的时间，甚至破坏了你准备已久的假期安排。于是，怒发冲冠的你开始密谋针对助教组的复仇计划，但是，助教组也不是任人欺负的病猫，你对助教组的每一次攻击都会引起助教组不同程度的不满。为了使问题更有趣，设你一开始的仇恨值为\(n\)，助教组的不满值为\(0\)，你有两种复仇计划可供选择（每种复仇计划都可以执行多次）：

(1) 仇恨值减1，助教组的不满值加A.

(2) 仇恨值除以k，助教租的不满值加B.

为了充分发泄你的情绪，你的最终仇恨值只能为1。而为了不过于得罪助教组，你想使助教组的不满值尽量小。

Input Format

四行，每行一个整数，分别表示\(n,k,A,B\)。

\(1 \leq n,k,A,B \leq 2\times 10^9\).

Output Format

一行一个整数表示在你最终仇恨值为1的情况下，助教组不满值的最小值。

Sample Input 1

19 3 4 2

Sample Output 1

12

Sample Input 2

19 19 19 1

Sample Output 2

1

ligongzzz's solution

#include <iostream>
using namespace std;

int main() {
    uint64_t n, k, A, B, ans = 0;
    cin >> n >> k >> A >> B;

    for (; n >= k && (n / k * k - n / k) * A >= B; n /= k) {
        ans += B + (n - n / k * k) * A;
    }
    ans += (n - 1ull) * A;
    cout << ans;

    return 0;
}

zqy2018's solution

#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, k, A, B;
void init(){
    n = read(), k = read(), A = read(), B = read();
}
void solve(){
    if (k == 1){
        printf("%lld\n", 1ll * (n - 1) * A);
        return ;
    }
    ll ans = 0;
    while (n > 1){
        if (n < k) {
            ans += 1ll * (n - 1) * A;
            break;
        }
        if (n % k == 0){
            int to = (n / k);
            if (1ll * (n - to) * A < B)
                ans += 1ll * (n - to) * A;
            else 
                ans += B;
            n = to;
        }else {
            int to = (n / k) * k;
            ans += 1ll * (n - to) * A;
            n = to;
        }
    }
    printf("%lld\n", ans);
}
int main(){
    init();
    solve();
    return 0;
}