10190 Divide, But Not Quite Conquer!

題目連結

題目敘述

你的目標是在這題中，將一個整數 n 持續除以另一個整數 m，直到 n = 1，並得到一個數列。

我們把這個數列的每個數稱作 a[i]，並假設這個數列總共有 k 個數（也就是說你必須進行 k - 1 次連續的除法才能讓 n 變成 1）。

你只有在滿足以下條件的情況下，才能建立這個數列：

• a[1] = n，a[i] = a[i - 1] ÷ m，對於所有 1 ≤ i < k。
• a[i] 可以被 m 整除（也就是 a[i] mod m = 0）對於所有 1 ≤ i < k。
• a[1] > a[2] > a[3] > ... > a[k]。

輸入格式

輸入將包含任意多行。
每一行包含兩個非負整數 n 和 m，它們的數值都小於 2,000,000,000。
你必須讀取直到檔案結束（EOF）為止。

輸出格式

對於每一組 n 和 m，你必須輸出對應的數列 a（如前面所定義）在同一行上，數列中的相鄰數字之間以一個空格分隔。

如果該數列因違反某項限制而不存在，請輸出字串 'Boring!'（不含引號），並且只輸出這一行。

解題思路

先檢查兩數是否為1或0，再用while迴圈確認是否能整除至1。

程式碼

#include <bits/stdc++.h>

using namespace std;

#define ll long long int

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    vector<ll> ans;
    ll n, m, boring;
    while (cin >> n >> m) {
        ans.clear();
        boring = 0;
        if (n == 0 || m == 0 || n == 1 || m == 1) {
            boring = 1;
        } else {
            while (n > 1) {
                if (n % m != 0) {
                    boring = 1;
                    break;
                } else {
                    ans.push_back(n);
                    n = n / m;
                }
            }
        }
        if (boring == 1) {
            cout << "Boring!" << '\n';
        } else {
            ans.push_back(1);
            for (auto i : ans) {
                if (i == 1) {
                    cout << i << '\n';
                } else {
                    cout << i << ' ';
                }
            }
        }
    }
}