HDU 3524 Perfect Squares：模 2^n 完全平方數計數與模逆元應用

題目大意

求模 2^n 下不同完全平方數的個數 f(n)，輸出 f(n) mod 10007。
範例：n=2 時序列 {i² mod 4} = 0,1,0,1...，故 f(2)=2。

數學規律推導

經觀察發現 n 奇偶性決定公式：

• n 為奇數：f(n) = 2 + (4^n - 1) / 3
• n 為偶數：f(n) = 2 + 2/3 × (4^(n/2 - 1) - 1)

模逆元處理除法

模 10007 (質數) 下，除以 3 等價乘以 3 的模逆元：

inv3 = 3^(10007-2) mod 10007  // 費馬小定理
     = powmod(3, 10005, 10007)

完整 C++ 解法

#include 
using namespace std;
typedef long long ll;
const int MOD = 10007;

ll mod_pow(ll a, ll e) {
    ll r = 1;
    while (e) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    const ll inv3 = mod_pow(3, MOD - 2); // 3 的模逆元
    int T; cin >> T;
    for (int ca = 1; ca <= T; ++ca) {
        ll n; cin >> n;
        ll ans;
        if (n & 1) { // 奇數
            ll t = (mod_pow(4, n/2) - 1 + MOD) % MOD;
            ans = (2 + t * inv3) % MOD;
        } else { // 偶數
            ll t = (mod_pow(4, n/2 - 1) - 1 + MOD) % MOD;
            ans = (2 + 2 * t % MOD * inv3) % MOD;
        }
        cout << "Case #" << ca << ": " << ans << "\n";
    }
    return 0;
}

關鍵點總結

1. 發現奇偶分治公式，避免大數直接計算
2. 模質數下除法轉乘法，使用快速冪求模逆元
3. 注意減法可能產生負數，需 +MOD 修正
4. n ≤ 2×10⁹，快速冪 O(log n) 滿足時限