[Codeforces] Codeforces Educational Round 66 (Div. 2) A. From Hero to Zero

2019年6月7日2020年9月8日

問題

方針

正の整数 \( n \) に対して、次の二つの操作を\( n \) が \( 0 \) になるまで行います。

1. \( n \) から \( 1 \) を引く
2. 正の整数 \( k \) が \( n \) を割ることができるとき、\( n \) を \( k \) で割る

このときの最小の操作回数を求めるには、2. の操作を行える時は行い、そうではないとき、1. の操作を行います。1. の操作を連続して行う回数は、\( n \bmod k \) です。このとき、\( n = n – n \bmod k \) となり、\( n – n \bmod k \) は \( k \) で割ることができます。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int t;
  ll n, k;
  cin >> t;
  for (int i = 0; i < t; i++) {
    cin >> n >> k;
    ll a = 0;
    while(n != 0) {
      if (n % k == 0) {
        n /= k;
        a++;
      } else {
        a += n % k;
        n -= n % k;
      }
    }
    cout << a << "\n";
  }
  return 0;
}