ZeroJudge 解題筆記：b594. A Marvelous Pet

作者：王一哲
日期：2025年7月28日


ZeroJudge 題目連結：b594. A Marvelous Pet

解題想法

這題比較直接的想法，是用兩個指針從小到大掃過一次，變數 low 從 1 到 n-2，變數 high 從 2 到 n-1，區間 [low, high] 之間的加總為 isum。每次更新時有三種可能性：

1. 如果 isum = n，答案 ans 加 1，再將整個區間向右平移，isum 減去 low，low 加 1，high 加 1，isum 加上 high。
2. 如果 isum > n，isum 減去 low，再將 low 加 1。
3. 如果 isum < n，high 加 1，再將 isum 加上 high。

這個寫法用 Python 會超時，用 C++ 可以過關。 另一種寫法會利用到等差級數和公式，假設首項為 $a$、項數為 $k$、公差為 $1$，級數和 $$ s = \frac{k[a + a + (k-1)]}{2} = \frac{k(2a+k-1)}{2} $$ 依照題目的要求 $s = n$、$a = 1$，上式的 $k$ 必須有正整數的解，因此 $$ 2n = k^2 + k ~\Rightarrow~ k^2 + k -2n = 0 ~\Rightarrow~ k = \frac{-1 \pm \sqrt{1 + 8n}}{2} $$ 要測試的 $k$ 值上限為 $$ k_{max} = \frac{\sqrt{1 + 8n} - 1}{2} $$ 先寫一個 for 迴圈，依序測試 $2 \leq k \leq k_{max}$，判斷 $k$ 值是否為解的步驟為

1. $mod(2n, k) = 0$
2. $tmp = \frac{2n}{k} - k + 1 > 0$
3. $mod(tmp, 2) = 0$
4. $a = \frac{tmp}{2}, a \leq 1, a+k-1 < n$

Python 程式碼

寫法1，超時。

import sys

def solve(n):
    low, high, isum, ans = 1, 2, 3, 0
    while low < n-1 and high < n:
        if isum == n:
            ans += 1
            isum -= low
            low += 1
            high += 1
            isum += high
        elif isum > n:
            isum -= low
            low += 1
        else:
            high += 1
            isum += high
    return ans

result = []
for line in sys.stdin:
    if not line.strip(): continue
    n = int(line)
    if n == 0: break
    ans = solve(n)
    result.append(f"{ans:d}\n")
sys.stdout.write("".join(result))

寫法2，使用時間約為 27 ms，記憶體約為 3.3 MB，通過測試。

import sys

for line in sys.stdin:
    if not line.strip(): continue
    n = int(line)
    if n == 0: break
    maxn = int(((1+8*n)**0.5 - 1)/2)
    ans = 0
    for k in range(2, maxn+1):
        num = 2*n  # 分子
        if num%k != 0: continue  # 條件1不合
        tmp = num//k - k + 1  # 暫存
        if tmp <= 0 or tmp%2 == 1: continue  # 條件2、3不合
        a = tmp//2  # 可能的 a 值
        if a >= 1 and a+k-1 < n: ans += 1  # 符合條件4，答案加 1
    print(ans)

C++ 程式碼

寫法1，使用時間約為 17 ms，記憶體約為 76 kB，通過測試。

#include <cstdio>
using namespace std;

int solve(int n) {
    int low = 1, high = 2, isum = 3, ans = 0;
    while(low < n-1 && high < n) {
        if (isum == n) {
            ans++;
            isum -= low;
            low++;
            high++;
            isum += high;
        } else if (isum > n) {
            isum -= low;
            low++;
        } else {
            high++;
            isum += high;
        }
    }
    return ans;
}

int main() {
    int n;
    while(scanf("%d", &n) != EOF && n != 0) printf("%d\n", solve(n));
    return 0;
}

寫法2，使用時間約為 2 ms，記憶體約為 124 kB，通過測試。

#include <cstdio>
#include <cmath>
using namespace std;

int main() {
    int n;
    while(scanf("%d", &n) != EOF && n != 0) {
        int maxn = int((sqrt(1+8*n)-1)/2.0), ans = 0;
        for(int k=2; k<=maxn; k++) {
            int num = 2*n;
            if (num%k != 0) continue;
            int tmp = num/k - k + 1;
            if (tmp <= 0 || tmp%2 == 1) continue;
            int a = tmp/2;
            if (a >= 1 && a+k-1 < n) ans++;
        }
        printf("%d\n", ans);
    }
    return 0;
}