b594 - A Marvelous Pet

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算有多少種方式，使得一組連續整數的和等於給定的數字 n，且這組數字至少包含兩個元素。這些整數代表 Mark 吃的東西的大小，Mark 每次吃的東西大小必須比上一次大 1。

解題思路

題目要求找到所有滿足以下條件的連續整數序列：

1. 序列中至少包含兩個數字。
2. 序列中所有數字的和等於 n。
3. 序列中的數字都是正整數，且小於 n。

程式碼使用兩層迴圈來枚舉連續整數序列的起始位置 i 和結束位置 j。對於每個序列，計算其和 k = (i + j) * (j - i + 1) / 2。如果 k 等於 n，則答案加 1。如果 k 大於 n，則跳出內層迴圈，因為後續的序列和只會更大。

複雜度分析

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

程式碼

#include <iostream>
using namespace std;
int n;
int main(){
	while(cin >> n){
		if(n==0)break;
		int ans=0;
		for(int i=1;i<n;++i){
			for(int j=i+1;j<n;++j){
				int k=(i+j)*(j-i+1)/2;
				if(k==n)
					++ans;
				else if(k>n)break;
			}
		}
		cout << ans << "\n";
	}
}