第九周周賽題解匯總：RMQ、DFS搜索、矩陣快速冪、大數GCD、進制轉換

A題：區間最大值查詢（HDU 5443 / The Water Problem）

題意：多測試用例，每組給定n個數，q次查詢區間[l,r]最大值。n,q≤1000。

解法：暴力O(nq)即可通過。大數據範圍下用線段樹/ST表（RMQ），單次查詢O(1)/O(log n)。

bool dfs(int i, int sum) {
    if (sum > k) return false;
    if (i == n) return sum == k;
    if (dfs(i+1, sum+a[i])) { st.push(a[i]); return true; }
    return dfs(i+1, sum);
}

C題：遞推數列模質數（T^T又有數學問題了）

題意：f1=1, f2=a^b, fn = a^b * f_{n-1}^c * f_{n-2}。求fn mod p。n≤10^18，p質數≤1e9+7。

思路：取對數/指數轉化為線性遞推：g(n) = c*g(n-1) + g(n-2) + 1。構造3×3矩陣快速冪求g(n)，再計算a^{g(n)} mod p。大指數需用費馬小定理/歐拉定理降冪：a^b mod p = a^{b mod (p-1)} mod p（a,p互質）。注意a mod p = 0特判。

E題：區間GCD（Complicated GCD / Codeforces 664A）

題意：求能整除[a,b]所有整數的最大整數。a,b≤10^100（大整數）。

解法：若a==b，答案為a；否則區間包含連續整數，GCD必為1。大整數用字符串比較。

F題：異進制下方程求解（Solve equation）
題意：給定C進制數A,B，轉十進制後求最大k使A = k*B + d（k,d非負整數）。
解法：字符串轉十進制（從高位遍歷，val = val*radix + digit，避免pow浮點誤差）。答案即k=A/B, d=A%B。