【題解】ZeroJudge e629: 11728 – Alternate Task

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=e629 (考生答對率: 38.27%)
【解題想法】

  • 找出因數和等於S的最大整數。
  • 從 S – 1 開始向下枚舉每一個整數 N,如果 N 的所有因數和等於 S,N即為答案。
  • N 的所有因數和,從 1 <= p <= sqrt(N),若 p 為 N 的因數,則必存在一數 q 為 N 的因數,且 p * q = N。
  • 當 p = q = sqrt(N),p 和 q 為相同的數,不重複加總。
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int S, Case = 1;
    while (cin >> S){
        if (S == 0) break;
        cout << "Case " << Case++ << ": ";
        if (S == 1){
            cout << "1\n";
            continue;
        }
        int ans = -1;
        for (int i = S-1; i >= 1; i--){
            int sum = 0;
            for (int j = 1; j <= sqrt(i); j++){
                if (i % j == 0){
                    sum += j;
                    if (j * j != i) sum+= i/j;
                }
            }
            if (sum == S){
                ans = i;
                break;
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

Python code (credit: Amy Chou)

Case = 1
while True:
    S = int(input())
    if S == 0:
        break
    print(f"Case {Case}: ", end="")
    Case += 1
    if S == 1:
        print(1)
        continue
    ans = -1
    for i in range(S-1, 0, -1):
        Sum = 0
        for j in range(1, int(i**0.5)+1):
            if i % j == 0:
                Sum += j
                if j*j != i:
                    Sum += i // j

        if Sum == S:
            ans = i
            break
    print(ans)
分享本文 Share with friends