ZeroJudge 解題筆記：f884. 柏恩的奶茶

作者：王一哲
日期：2025年10月27日


ZeroJudge 題目連結：f884. 柏恩的奶茶

解題想法

這題考數學，要先推導公式。依照題意，給定某個正整數 $n$，要找到另一個正整數 $x$，使 $x(x+1)(x+2)(x+3) + 1 = x$。先化簡算式 $$ x(x+1)(x+2)(x+3) + 1 = x^4 + 6x^3 + 11x^2 + 6x + 1 = (x^2 + 3x + 1)^2 $$ 因此題目可以改為求 $$ (x^2 + 3x + 1)^2 = n $$ 因為題目要求 $n, x \in N$，所以 $n$ 一定是平方數，假設 $x^2 + 3x + 1 \equiv k$，則 $k = \sqrt{n}$。在程式碼之中，可以先檢查

k = math.isqrt(n)  # Python 3.11 之後的寫法，舊版可用 k = int(math.sqrt(n))
if k*k != n:
    print(-1); return

將題目由解一元四次方程化簡為解一元二次方程式 $$ x^2 + 3x + 1 - k = 0 $$ 判別式 $$ D = 3^2 - 4\times(1-k) = 5 + 4k $$ 因為 $x$ 要有正整數解，$D = 5 + 4k$ 為平方數，$\sqrt{D} = \sqrt{5 + 4k}$ 為奇數且大於 3。由公式解可得 $$ x = \frac{-3 + \sqrt{5 + 4k}}{2} = \frac{-3 + \sqrt{5 + 4 \sqrt{n}}}{2} $$ 在程式碼之中，可以先檢查

d = math.isqrt(5+4k)  # Python 3.11 之後的寫法，舊版可用 d = int(math.sqrt(5+4k))
if d*d != k:
    print(-1); return
if (5+4*k)%2 == 0 or 5+4*k <= 3:
    print(-1); return

最後將題目給的 $n$ 值代入公式求解。題目看起來保證測資一定有解，以上三個檢查是否有解的部分可以跳過，直接代公式求解。

Python 程式碼

使用時間約為 0.5 s，記憶體約為 6.2 MB，通過測試。

import sys, math

for line in sys.stdin:
    n = int(line)
    x = (-3+int(math.sqrt(5 + 4*int(math.sqrt(n)))))//2
    print(x, x+1, x+2, x+3)

C++ 程式碼

使用時間約為 74 ms，記憶體約為 136 kB，通過測試。

#include <cstdio>
#include <cmath>
typedef unsigned long long LL;
using namespace std;

int main() {
    LL n;
    while(scanf("%llu", &n) != EOF) {
        LL x = (-3+LL(sqrt(5 + 4*LL(sqrt(n)))))/2;
        printf("%llu %llu %llu %llu\n", x, x+1, x+2, x+3);
    }
    return 0;
}