A Sequence of Numbers - 等差/等比數列第 K 項快速冪取模

問題描述

給定數列前三項，判斷是等差或等比數列，求第 K 項模 200907。K ≤ 10⁹，前三項 < 2⁶³。

解法

若 2*a2 == a1 + a3 為等差，公差 d = a2-a1，第 K 項 = a1 + (K-1)*d。
否則為等比，公比 q = a2/a1，第 K 項 = a1 * q^{K-1}。
用快速冪計算 q^{K-1} mod 200907，注意取模乘法防溢出（用 long long 或 __int128）。

快速冪模板

long long mod_pow(long long a, long long n, long long mod) {
    long long r = 1;
    while (n) {
        if (n & 1) r = r * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return r;
}