華為 OJ 猴子分桃：數學規律求最少桃子數

題目簡介

n 只猴子（n ≤ 20）依次分桃：每次分成 5 堆多 1 個，給老猴子 1 個，拿走 1 堆。最後剩下的全給老猴子。求初始最少桃子數和老猴子最終得到的桃子數。

數學推導

設第 i 次分桃前桃子數為 a_i，則 a_{i+1} = (a_i - 1) * 4/5。逆推得通項：a_1 = 5^n - 4。老猴子最終得到：n + (4/5)^n * (5^n - 4)。

代碼實現

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

int main() {
    int n;
    while (cin >> n && n) {
        long long total = 1;
        for (int i = 0; i < n; i++) total *= 5;
        total -= 4;
        long long old = n;
        long long cur = total;
        for (int i = 0; i < n; i++) cur = (cur - 1) / 5 * 4;
        old += cur;
        cout << total << " " << old << endl;
    }
    return 0;
}

測試樣例

輸入：5 → 輸出：3121 1025
輸入：1 → 輸出：1 1