d619 - 奇摩知識

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算從 1 到 n 的整數中，每個整數的二進制表示中 1 的個數之和，並將結果模 1000000000。

解題思路

題目要求計算 1 到 n 的每個數字的二進制表示中 1 的個數之和。直接遍歷 1 到 n 並計算每個數字的 1 的個數會導致時間超時。 觀察到對於 2 的冪次，例如 2, 4, 8, 16...，其二進制表示中只有一個 1。 對於 2 的冪次之前的數字，例如 1, 2, 3, 4, 5, 6, 7, 8...，可以發現 1 的個數的模式。 例如，對於 n = 12，可以分解為：

• 1 到 8 的 1 的個數之和
• 9 到 12 的 1 的個數之和 程式碼中，ba 從 4 開始，每次乘以 ba，表示 2 的冪次。 ans+=n/ba*(ba/2)+max(n%ba+1-ba/2,(long long)0); 這行程式碼計算了在 ba 的倍數中，1 的個數的貢獻。 n / ba 表示有多少個完整的 ba。 ba / 2 表示每個完整的 ba 中 1 的個數。 n % ba 表示剩餘的數字。 max(n % ba + 1 - ba / 2, (long long)0) 計算剩餘數字中 1 的個數的貢獻。

複雜度分析

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

程式碼

#include <iostream>
using namespace std;
long long n,ans,ba;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	while(cin >> n){
		ans=(n+1)/2;
		for(ba=4;ba<=200000000;ba+=ba){
			ans+=n/ba*(ba/2)+max(n%ba+1-ba/2,(long long)0);
		}
		cout << ans%1000000000 << "\n";
	}
}