HDU 2601 An easy problem - 數學轉化求約數個數

問題描述

給定 N，求正整數對 (i, j) 滿足 N = i*j + i + j 的方案數。

數學轉化

N = i*j + i + j ⇔ N + 1 = i*j + i + j + 1 = (i+1)(j+1)。

令 x = i+1, y = j+1，則 x*y = N+1，且 x, y ≥ 2。方案數即為 N+1 的因子對數，其中因子 > 1。

等價於 N+1 的約數個數減 1（去掉 1），再除以 2（無序對）。但題目中 i,j 為正整數，x,y≥2，且 (i,j) 有序？原題通常視為無序對，即計算 N+1 的約數個數（不含 1）的一半。

代碼實現（C++）

#include 
#include 
using namespace std;

int main() {
    int T; cin >> T;
    while (T--) {
        long long n; cin >> n;
        n++; // N+1
        int cnt = 0;
        for (long long i = 2; i * i <= n; i++) {
            if (n % i == 0) cnt++;
        }
        cout << cnt << endl;
    }
    return 0;
}

注意：循環從 2 開始，計算因子對數。若 n 為完全平方數，平方根因子只計一次，符合無序對邏輯。