AtCoder ABC 372 B - 3^A (5Q, 灰色, 200 点)

三進法をテーマにした問題！

• 問題へのリンク

問題概要

正の整数 が与えられる。以下の条件を全て満たす正の整数 と非負整数列 を 1 つ求めよ。

• 
• 
• 

制約

• 

考えたこと

問題文が一見わかりにくいかもしれない。こういうときは具体的にやってみよう。

たとえば のとき、47 を三進法で表すと、1202 となる。このことは、

と表せることを意味する。

一般に、整数 を考える。 を三進法で表したとき、 の位の値の個数に応じて を足していけばよいことがわかる。

を三進法で表すためには、

---

• を 3 で割った余りを求める
• を 3 で割った商で置き換える

---

という操作を繰り返していけば良い。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int M, offset = 0;
    cin >> M;
    vector<int> res;
    while (M) {
        for (int i = 0; i < M % 3; i++) res.push_back(offset);
        M /= 3;
        offset++;
    }
    cout << res.size() << endl;
    for (int i = 0; i < res.size(); i++) cout << res[i] << " ";
    cout << endl;
}