題目大意是給定一些(n)青蛙及其跳躍的步數和方法，給定一些石頭，編號從1~m，問所有曾經被青蛙跳過的石頭的編號的和。

　　思路

　　　　容斥定理

　　從題目中很容易得出每一個青蛙的跳過的石頭編號是k * gcd(m, frog_i) {m/ gcd(m, frog_i) >= k >= 1}，這樣用等差數列求和公式就能求出

　　每一個青蛙所跳過的石頭編號的和。但是有一些石頭是被重復計算的。這樣就用到了容斥原理

　　wiki百科 https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle

　　訓練時沒有做出來，參考了大牛的思路。http://www.cnblogs.com/Quinte/p/4932471.html

　　可以先把m所有的因子求出來，排好序。 對于每一個是青蛙跳過的石頭編號的倍數的因子進行標記，表示該因子做了貢獻，

　　做貢獻的次數用一個數組或者map保存起來，然后把所有因子從小到大進行掃描，如果當前因子要做貢獻，則進行加和，同

　　時把所有是該因子倍數的因子要加和的次數減去當前因子做貢獻的次數。

#include <cstdio> #include <cstring> #include <algorithm> #include <set> #include <vector> #include <map> #include <cmath> using namespace std; typedef long long LL; const int maxn = 100000 + 10; int n, m; int f[maxn]; bool vis[maxn]; map<int, int> times;int gcd(int a, int b){return a == 0 ? b : gcd(b % a ,a); }LL solve(){LL sum = 0;vector<int> fact;times.clear();memset(vis, false, sizeof vis);for(int i = 1; i <= int(sqrt(m) + 0.5); ++i){if(m % i == 0) {fact.push_back(i); times[i] = 0;if(i * i != m) {fact.push_back(m / i); times[m / i] = 0;}}}sort(fact.begin(), fact.end());for(int i = 0; i < n; ++i){int x = gcd(f[i], m);for(int j = 0; j < fact.size(); ++j){if(fact[j] % x == 0) vis[j] = true;}}fact.pop_back();//Inclusion_exclusion principlefor(int i = 0; i < fact.size(); ++i){if((int)vis[i] != times[i]){int t = m / fact[i];sum += (LL)t * (t - 1) * fact[i] / 2 * ((int)vis[i] - times[i]);t = vis[i] - times[i];for(int j = i + 1; j < fact.size(); ++j){if(fact[j] % fact[i] == 0) times[j] += t;}}}return sum; }int main() {int T; scanf("%d", &T);int kase = 0;while(T --){ scanf("%d %d", &n, &m);for(int i = 0; i < n; ++i ){scanf("%d",&f[i]);}printf("Case #%d: %I64d\n", ++kase, solve());}return 0; }

總結

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

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