e566 - 10190 - Divide, But Not Quite Conquer!

🔗 前往 ZeroJudge 原題

題目描述

題目要求判斷給定的兩個整數 n 和 k，是否存在一個序列 a，滿足 a[1] = n，a[i] = a[i-1] / k，且序列中所有元素都能被 k 整除，並且序列是嚴格遞減的。如果存在這樣的序列，則輸出該序列，否則輸出 "Boring!"。

解題思路

題目要求找到一個整數序列，該序列通過不斷地將前一個數除以 k 得到，並且序列中的每個數都能被 k 整除。我們可以通過迭代的方式來生成序列，並檢查是否滿足條件。首先，如果 k 等於 0 或 1，則序列必然不存在，輸出 "Boring!"。否則，我們不斷地將 n 除以 k，直到 n 小於 k 為止。在每次除法後，我們檢查結果是否能被 k 整除。如果最終 n 等於 k 的某個冪次，則序列存在，我們按照序列的生成順序輸出序列。否則，序列不存在，輸出 "Boring!"。

複雜度分析

• 時間複雜度: O(log_k(n))
• 空間複雜度: O(1)

程式碼

#include <iostream>
#include <string>
using namespace std;
int main(){
	long long int n,k;
	while(cin >> n >> k){
		long long int kk=k; 
		if(k==0||k==1){
			cout << "Boring!\n";
		}
		else{
			while(n>kk)
				kk*=k;
			if(kk==n){
				cout << n;
				while(n!=1){
					cout << " " << n/k;
					n/=k;
				}
				cout << "\n";
			}
			else
				cout << "Boring!\n";
		}
	}
}