b133 - NOIP2006 4.数列

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算一個由 k 的冪次方及其組合構成的遞增序列的第 N 項。序列中的每一項都是 k 的 0 次方到某次方的和，且這些冪次方互不相等。例如，當 k=3 時，序列為 1, 3, 4, 9, 10, 12, 13,...。

解題思路

這題的核心思想是將 N 轉換為 k 進位制。由於序列中的每一項都可以表示為 k 的冪次方的組合，因此第 N 項的值實際上就是 N 在 k 進位制下的表示，然後將其轉換回十進位制。程式碼首先將 N 轉換為二進位制（因為題目中 k 最大為 15，所以使用 bool 陣列儲存二進位制數），然後根據二進位制數的每一位，計算對應的 k 的冪次方，並將它們加總，得到最終的結果。

複雜度分析

• 時間複雜度: O(logk(N))，其中 k 是給定的底數，N 是要查找的項。這是因為將 N 轉換為 k 進位制需要 logk(N) 的時間。
• 空間複雜度: O(logk(N))，因為需要儲存 k 進位制表示的數字。

程式碼

#include <iostream>
using namespace std;
int main(){
	int k,n;
	while(cin >> k >> n){
		int it=0,ans=0;
		bool a[11]={0};
		while(n){
			a[it]=n%2;
			n/=2;
			++it;
		} 
		for(int i=0,kk=1;i<it;++i,kk*=k)
			ans+=a[i]*kk;
		cout << ans << "\n"; 
	}
}