d224 - 11296 - Counting Solutions to an Integral Equation

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算非負整數解 x, y, z 滿足方程式 x + 2y + 2z = n 的解的數量，其中 n 是輸入值。

解題思路

方程式 x + 2y + 2z = n 可以改寫為 x = n - 2(y + z)。由於 x 必須是非負整數，因此 n - 2(y + z) >= 0，即 y + z <= n/2。 令 k = y + z，則 k 的範圍是 0 到 n/2。對於每個 k 值，y 和 z 的非負整數解的數量是 k + 1。 因此，總解的數量是從 k = 0 到 n/2 的 (k + 1) 的總和，即 (0 + 1) + (1 + 1) + ... + (n/2 + 1)。 這個總和可以使用公式 (m * (m + 1)) / 2 計算，其中 m = n/2。 由於 n/2 可能不是整數，因此我們使用 n/2 + 1 作為 m 的值，以確保計算正確。

複雜度分析

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

程式碼

#include <iostream>
using namespace std;
int main(){
	int n;
	while(cin >> n){
		long long int m=n/2+1;
		cout << (m+1)*m/2 << "\n";
	}
}