s137 - 第四個因數

🔗 前往 ZeroJudge 原題

題目描述

題目要求找到一個四位數 N，使得 1 + sqrt(N+1) 是 N 的所有因數中由小到大排序的第四個因數。如果符合條件的 N 不只一個，則輸出最小的那個。

解題思路

由於 N 是四位數，因此 1000 <= N < 10000。我們可以從 1000 開始迭代，檢查每個 N 是否滿足條件。對於每個 N，首先計算 1 + sqrt(N+1)。然後計算 N 的所有因數，並將它們排序。如果 1 + sqrt(N+1) 是排序後的因數列表中的第四個元素，則 N 就是我們要找的答案。如果沒有找到符合條件的 N，則輸出 -1。

程式碼中 ok(int x) 函數用於判斷一個數 x 是否滿足題目條件。首先，它檢查 x+1 是否為完全平方數。如果是，則計算平方根 sv 並加 1，得到可能的第四個因數。然後，它計算 x 的因數個數 ct。如果 ct 等於 4，則表示 x 滿足條件，返回 true，否則返回 false。

主函數 main() 從 1000 迭代到 9999，對於每個數字 i，調用 ok(i) 函數檢查是否滿足條件。如果找到符合條件的數字，則輸出該數字並立即返回。如果迭代完成後仍然沒有找到符合條件的數字，則輸出 -1。

複雜度分析

• 時間複雜度: O(N * sqrt(N))，其中 N 是 10000。因為需要迭代 1000 到 9999 之間的每個數字，並且對於每個數字，需要計算平方根和因數。
• 空間複雜度: O(1)，因為程式碼只使用了常數級別的額外空間。

程式碼

#include <iostream>
#include <cmath>
using namespace std;
bool ok(int x){
	int sv = sqrt(x+1);
	if((x+1)!=(sv*sv))return 0;
	++sv;
	int ct=0;
	for(int j=1;j<=sv;++j){
		if(x%j==0){
			++ct;
		}
	}
	if(ct==4)return 1;
	return 0; 
}
int main(){
	for(int i=1000;i<10000;++i){
		if(ok(i)){
			cout << i;
			return 0;
		}
	}
	cout << "-1";
	return 0;
}