題意

傳送門 HDU 5514

題解

對于青蛙 $i$，每一步即在模 $m$ 意義上增加 $a_i$，那么當青蛙走回起點 $0$ 時，有 $$a_i\times step=0\mathrm{m}\mathrm{o}\mathrm{d}m$$ 顯然最小的步數為 $m/gcd(a_i,m)$，那么步長為 $gcd(a_i,m)$。青蛙可能的步長只能是 $m$ 的約數，約數個數的上界為 $2\sqrt{m}$，這是一個寬松的上界，實際上 $10^9$ 內的數字其約數個數僅 $10^3$ 級別。考慮對約數進行處理。

設約數數組為 $D$，使之有序。枚舉每一只青蛙，標記滿足 $gcd(a_i,m)|D_j$ 的約數。從小到大枚舉約數，以其為步長，根據等差數列求和公式可以得到被這個步長標記的石子編號的和；根據容斥原理，約數 $D_j$ 會被滿足 $D_i|D_j,i<j$ 的約數重復統計，那么減去重復統計的部分，同時對滿足 $D_j|D_k,j<k$ 的約數記錄 $D_j$ 對其重復計數的數量。設 $m$ 的約數個數為 $d$，時間復雜度 $O(t{d}^2)$。

#include <algorithm> #include <cstdio> #include <cstring> using namespace std; typedef long long ll; const int maxd = 1600, maxn = 10005; int T, N, M, A[maxn], D[maxd], cnt[maxd]; bool used[maxd];int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }int main() {scanf("%d", &T);for (int c = 1; c <= T; ++c){scanf("%d%d", &N, &M);for (int i = 0; i < N; ++i)scanf("%d", A + i);memset(used, 0, sizeof(used));memset(cnt, 0, sizeof(cnt));int d = 0;for (int i = 1; i * i <= M; ++i)if (M % i == 0){D[d++] = i;if (M / i != i)D[d++] = M / i;}sort(D, D + d);for (int i = 0; i < N; ++i){int g = gcd(M, A[i]);for (int j = 0; j < d; ++j)if (D[j] % g == 0)used[j] = 1;}ll res = 0;for (int i = 0; i < d; ++i)if (used[i]){int k = D[i], x = (M - 1) / k, n = 1 - cnt[i];res += (ll)(x + 1) * x / 2 * k * n;for (int j = i + 1; j < d; ++j)if (used[j] && D[j] % k == 0)cnt[j] += n;}printf("Case #%d: %lld\n", c, res);}return 0; }

總結

以上是生活随笔為你收集整理的HDU 5514 容斥原理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。