e629 - 11728 - Alternate Task

🔗 前往 ZeroJudge 原題

題目描述

題目要求對於給定的正整數 S，找到一個正整數 N，使得 N 的所有因數之和等於 S。如果存在多個滿足條件的 N，則輸出其中最大的那個。如果不存在滿足條件的 N，則輸出 -1。

解題思路

這題的解題思路是先預處理出所有可能的因數和，然後再查詢。具體來說，我們遍歷 1 到 1000 的所有數字 i，計算 i 的所有因數之和。將因數和作為陣列的索引，將 i 作為陣列的值。然後，對於每個輸入的 S，我們直接查詢陣列中索引為 S 的值，即為答案。如果陣列中索引為 S 的值為 -1，則表示不存在滿足條件的 N，輸出 -1。

預處理時，計算因數和的效率可以優化。只需要遍歷到平方根即可，如果 i % j == 0，則 j 和 i / j 都是 i 的因數。需要注意的是，如果 i 是完全平方數，則平方根只應該加一次。

複雜度分析

• 時間複雜度: O(1000 * sqrt(1000)) for precomputation + O(1) per query. 整體來說，可以視為 O(1)
• 空間複雜度: O(1001)

程式碼

#include <iostream>
#include <cmath>
using namespace std;
int s,ca,ans[1001];
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	for(int i=0;i<1001;++i)
		ans[i]=-1;
	for(int i=1;i<1001;++i){
		int tmp=0,sqi=sqrt(i);
		for(int j=1;j<=sqi;++j)
			if(i%j==0){
				tmp+=j;
				tmp+=i/j;
			}
		if(sqi*sqi==i)
			tmp-=sqi;
		if(tmp<1001)
			ans[tmp]=i;
	}
	while(cin >> s){
		if(s==0)break;
		cout << "Case " << ++ca << ": " << ans[s] << '\n';
	}
}