11728 Alternate Task

題目連結

題目敘述

Hasan 喜歡和朋友們玩數字遊戲。 有一天，他們玩一個遊戲：其中一人說出一個正整數，其餘的人必須說出這個數字的所有因數的總和。 第一個正確說出來的人獲勝。

他們覺得這個遊戲有點無聊，想試試不同的玩法。 Hasan 建議嘗試反過來玩這個遊戲。 也就是說，給定一個正整數 S，他們要找出一個數字，其所有因數的總和是 S。

他們意識到這個任務比原來的遊戲難多了，於是 Hasan 向你求助。 幸運的是，Hasan 擁有一個可攜式可編程的裝置，你決定為這個裝置寫一個程式。 給定一個數值 S 作為程式輸入，程式將輸出一個其因數總和等於 S 的數字。

輸入格式

每組輸入由一個正整數 S 組成 (S ≤ 1000)。 最後一組輸入是一個數值 0，表示輸入結束。

輸出格式

對於輸入的每個 S，輸出一行結果。 輸出一個正整數，其因數的總和等於 S。 若有多個這樣的數字，輸出其中最大的那個。 若沒有符合條件的數字，輸出 -1。

解題思路

fsum 回傳所有因數和，因為要找最大的 i，我們可以從 i = 1000 倒著往下找，直到找到第一個 fsum(i) == N 的數，若 i == 1 輸出 -1 代表沒有符合條件的數字。

程式碼

#include<bits/stdc++.h>
using namespace std;

int fsum(int a) {
    int s = 0;
    for (int i = 1; i * i <= a; i++) {
        if (a % i == 0) {
            s += i;
            if (i != a / i) {
                s += a / i;
            }
        }
    }
    return s;
}

int main() {
    int n, c = 0;
    while(cin >> n && n) {
        c++;
        for (int i = n; i >= 1; i--) {
            if (fsum(i) == n) {
                cout << "Case " << c << ": " << i << "\n";
                break;
            }
            if (i == 1){
                cout << "Case " << c << ": " << -1 << "\n";
            }
        }
    }
}