Bình luận

• 
  

  16

  

  tronglee  đã bình luận lúc 6, Tháng 10, 2025, 13:23

  SPOIL!!!

  💡 Hướng tiếp cận

  Ta cần đưa số X về 1 bằng hai thao tác:

  • Thao tác 1: Nếu X chia hết cho K thì chia X cho K.
  • Thao tác 2: Nếu không chia hết, thì tăng X lên 1 đơn vị.

  Vì chỉ được tăng (không giảm), ta sẽ thực hiện theo quy trình tham lam (greedy):

  • Nếu X % K == 0 thì chia (X /= K).
  • Ngược lại, tăng X lên (X++).

  Lặp lại đến khi X == 1.

  Mỗi lần ghi lại thao tác (1 nếu chia, 2 nếu tăng).

  ✅ Code

  #include <bits/stdc++.h>
  using namespace std;
  const long long N = 1e5 + 5;
  
  long long n, k;
  int a[N];
  
  int main() {
      ios::sync_with_stdio(false);
      cin.tie(nullptr);
  
      cin >> n >> k;
      int i = 0;
  
      while (n > 1) {
          i++;
          if (n % k == 0) {
              n /= k;
              a[i] = 1;
          } else {
              n++;
              a[i] = 2;
          }
      }
  
      cout << i << '\n';
      for (int j = 1; j <= i; j++)
          cout << a[j] << ' ';
  
      return 0;
  }