Codeforces 476C Dreamoon and Sums - 數學公式推導 O(1) 解

題目大意

給定 a, b。正整數 x 為 nice number，若 ⌊x/b⌋ / (x mod b) ∈ [1, a] (整數除法)。求所有 nice number 的和模 1e9+7。

數學推導

設 x = q·b + r，其中 q = ⌊x/b⌋, r = x mod b (1 ≤ r ≤ b-1)。
條件：q / r = k，其中 k ∈ [1, a] 整數。即 q = k·r。
則 x = k·r·b + r = r·(k·b + 1)。

對固定 k，r 遍歷 1..b-1，所有 x 之和：

∑_{r=1}^{b-1} r·(k·b + 1) = (k·b + 1) · ∑_{r=1}^{b-1} r = (k·b + 1) · b(b-1)/2

再對 k = 1..a 求和：

Ans = b(b-1)/2 · ∑_{k=1}^a (k·b + 1)
    = b(b-1)/2 · ( b·∑k + ∑1 )
    = b(b-1)/2 · ( b·a(a+1)/2 + a )
    = b(b-1)/2 · a · ( b(a+1)/2 + 1 )

模運算實現

const long long MOD = 1e9+7;
long long a, b;
long long sum_k = a * (a + 1) / 2 % MOD;
long long term = (b % MOD) * sum_k % MOD;
term = (term + a) % MOD; // b·∑k + a
long long B = b * (b - 1) / 2 % MOD;
long long ans = B * term % MOD;

完整代碼

#include 
using namespace std;
const long long MOD = 1000000007;

int main() {
    long long a, b;
    while (cin >> a >> b) {
        long long sum_k = a * (a + 1) / 2 % MOD;
        long long term = (b % MOD) * sum_k % MOD;
        term = (term + a) % MOD;
        long long B = b * (b - 1) / 2 % MOD;
        long long ans = B * term % MOD;
        cout << ans << '\n';
    }
    return 0;
}

複雜度

• 時間：O(1) 每測資。
• 空間：O(1)。