b679 - 棄屍 (16+)

🔗 前往 ZeroJudge 原題

題目描述

題目給定一個數字 X，代表金字塔中學長的總數量。要求計算出金字塔的高度 H。金字塔的每一層學長數量依序為 1, 3, 5, 7, ...，即第 i 層有 2*i - 1 個學長。

解題思路

金字塔的總學長數量可以表示為 1 + 3 + 5 + ... + (2H - 1)。這個等差數列的和為 H^2。因此，題目要求解 H^2 = X 的 H 值。由於輸入的 X 是 long long int，直接開根號可能會溢位。題目中給定的範例暗示了可以利用 a=sqrt(a<<1) 來計算。a << 1 等同於 a * 2，因此 sqrt(a << 1) 等同於 sqrt(2 * a)。但題目實際上要求的是 sqrt(X)，所以這個公式並不適用。正確的解法是直接計算 sqrt(X) 並將結果輸出。

複雜度分析

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

程式碼

#include <iostream>
#include<cmath>
using namespace std;
int main(int argc, char** argv) {
long long int a;
while(cin>>a){
a=sqrt(a<<1);
cout<<a<<"\n";
}
}