題意#
題目給定長度為 \( n \) 的整數陣列。
需要求出有幾個「連續子陣列（Subarray）」的數字總和可被 \( n \) 整除（即除以 \( n \) 的餘數為 0）。
思路#
子陣列 [L, R] 的總和可表示為 pre[R] - pre[L-1]。
若該總和能被 \( n \) 整除，則滿足：
\( (\text{pre}[R] - \text{pre}[L-1]) \pmod n \equiv 0 \)
依據同餘性質，上式等價於：
\( \text{pre}[R] \pmod n \equiv \text{pre}[L-1] \pmod n \)
這意味著，只需關注「每個前綴和除以 \( n \) 的餘數」。
當某位置的前綴和餘數，與過去某位置的前綴和餘數相同時，兩者之間的子陣列總和必能被 \( n \) 整除。
實作流程如下：
- 建立大小為 \( n \) 的陣列
cnt，記錄每個餘數出現的次數。初始化cnt[0] = 1，代表初始狀態下餘數為 0 發生過一次。 - 遍歷陣列計算前綴和，並求取對於 \( n \) 的餘數。
- 由於 C++ 中負數取餘的結果可能為負，因此需要使用
(pre[i] % n + n) % n將餘數轉換為正數。 - 取得正確的餘數後，查詢
cnt中該餘數出現過的次數並累加至答案，接著更新該餘數的計數。
整體時間複雜度為 \(\mathcal{O}(N)\)。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
signed main() { WA();
int n; cin >> n;
vector<int> v(n);
for (auto &i : v) cin >> i;
int ans = 0;
// pre 用來記錄前綴和，cnt 用來統計「每個餘數」曾經出現過的次數
vector<int> pre(n+1), cnt(n);
// 初始化 `cnt[0]` 為 1，代表前綴和為 0 的初始狀態
cnt[0] = 1;
// 計算前綴和
for (int i = 1; i <= n; i++) pre[i] = v[i-1]+pre[i-1];
for (int i = 1; i <= n; i++) {
// 處理 C++ 負數取餘的轉換
int now = (pre[i]%n+n)%n;
// 若餘數相同，代表兩者差距可被 n 整除
ans += cnt[now];
// 登記該餘數供新子陣列配對
cnt[now]++;
}
// 輸出答案
cout << ans;
}
// 核心精神：(pre[R] - pre[L-1]) % n == 0 => pre[R] % n == pre[L-1] % n
