原題傳送門

題意：

有n只青蛙，m塊石頭呈環放置（從0~m-1標記），第i只青蛙每次跳ai步，跳躍次數無限制。求被n只青蛙踩過的石頭的下表和

思路1（歐拉函數）：

很明顯，對于第i只青蛙，被踩的石頭的編號一定是gcd（ai， m）的倍數，那么我們先將ai轉換為gcd（ai，m）
然后對于第 j 塊石頭，我們定義它只能被跳躍步數為x的青蛙踩中（x滿足gcd（m，j）= x）例如下面的樣例：

2 12

9 10

那么這個樣例之中被踩過并且有貢獻的石頭編號為2，3，4，6，8，9，10

按照我們的定義

2 10 是被跳躍步數為2的青蛙踩過

3 9 是被跳躍步數為3的青蛙踩過

4 8 是被跳躍步數為4的青蛙踩過

6 是被跳躍步數為6的青蛙踩過

這里的青蛙只有兩個，但是我們可以造兩個步數為4 和 6的青蛙，這對答案是完全沒有影響的
因此 x 的答案貢獻為 m以內 ∑ j [gcd（m，j）== x]
由gcd（m，j）= x，可以得到gcd（m/x，j/x）= 1，即（j/x）為（m/x）內所有與（m/x）互素的數
那么上面對于x的答案貢獻就轉換為 x * ∑ i [gcd（m/x，i）== 1]

知識點：設小于n的所有與n互質的數的和為Sum，Sum=n?φ(n)/2

證明：

1. gcd（x，n）= 1，那么gcd（n-x，n）= 1同樣滿足

2. 可見n以內與n互素的數字都是成對出現的，而素數對的個數就是φ(n)/2，并且每一對素數和為n

證畢

由此x的答案再次變換為

x *（φ（m/x）/ 2 *（m/x））

稍稍化簡得到

φ（m/x）/ 2*m

到這里就可以直接枚舉m的因子，看跳躍步數為當前的因子fac青蛙能否被構造（fac % ai == 0）即可

AC代碼1：

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e4 + 9;int a[N], fac[N];int Euler (int n) {ll res = n;for (int i = 2; i * i <= n; i++) {if (n % i == 0) {res = res / i * (i - 1);while (n % i == 0) {n /= i;}}}if (n > 1) {res = res / n * (n - 1);}return res; }int get_fac(int n) {int len = 0;for (int i = 2; i * i <= n; i ++) {if (n % i == 0) {fac[len++] = i;if (i * i != n) {fac[len++] = n / i;}}}sort (fac, fac + len);return len; }int main() {int T, cnt = 1;scanf ("%d", &T);while (T --) {int n, m;bool flag = false;scanf ("%d%d", &n, &m);int len = get_fac(m);for (int i = 0; i < n; i ++) {scanf ("%d", a + i);a[i] = __gcd(a[i], m);if (a[i] == 1) {flag = true;}}ll ans = 0;for (int i = 0; i < len; i ++) {for (int j = 0; j < n; j ++) {if (fac[i] % a[j] == 0) {ans += 1ll * Euler(m/fac[i]) * m / 2 ;break;}}}printf ("Case #%d: ", cnt ++);if (flag) {cout << 1ll * m * (m - 1) / 2 << endl;} else {cout << ans << endl;}}return 0; }

思路2（容斥原理）：

首先預處理出m的所有因子，每個因子的答案貢獻次數初始化為1，然后根據容斥原理去調節后續每個因子的答案貢獻次數。例如下面的樣例：

2 24

9 10

24的所有因子為 2，3，4，6，8，12

初始化所有因子的答案貢獻為1
計算2的答案貢獻的時候，2的答案貢獻次數為1，因此4，6，8，12的答案貢獻次數 -1
計算3的答案貢獻的時候，3的答案貢獻次數為1，6和12的答案貢獻次數-1
計算4的答案貢獻的時候，4的答案貢獻次數為1，8和12的答案貢獻次數-1
（！高潮來了！）
計算6的答案貢獻的時候，答案貢獻次數為-1，這個時候12的答案貢獻次數 -（-1）也就是+1
計算8的答案貢獻的時候，答案貢獻次數為-1，后續因子沒有8的倍數，因此無須調節其他因子的答案貢獻次數
計算12的答案貢獻的時候，答案貢獻次數為-1，與上面同理
（容斥原理真奇妙）

AC代碼2：

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e4 + 9;int a[N], vis[N], fac[N];int init(int n) {memset (vis, 0, sizeof vis);int len = 0;for (int i = 2; i * i <= n; i ++) {if (n % i == 0) {fac[len++] = i;if (i * i != n) {fac[len++] = n / i;}}}sort (fac, fac + len);return len; }int main() {int T, cnt = 1;scanf ("%d", &T);while (T --) {int n, m;bool flag = false;scanf ("%d%d", &n, &m);int len = init(m);for (int i = 0; i < n; i ++) {scanf ("%d", a + i);a[i] = __gcd(a[i], m);if (a[i] == 1) {flag = true;}for (int j = 0; j < len; j ++) {if (fac[j] % a[i] == 0) {vis[j] = 1;}}}ll ans = 0;for (int i = 0; i < len; i ++) {ll res = m / fac[i];ans += res * (res - 1) / 2 * fac[i] * vis[i];for (int j = i + 1; j < len; j ++) {if (fac[j] % fac[i] == 0) {vis[j] -= vis[i];}}}printf ("Case #%d: ", cnt ++);if (flag) {cout << 1ll * m * (m - 1) / 2 << endl;} else {cout << ans << endl;}}return 0; }

(PS.以上的答案貢獻計算都是O(1)的)

總結

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

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