题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5514
题意：有m个石子围成一圈, 有n只青蛙从跳石子, 都从0号石子开始, 每只能越过xi个石子。问所有被至少踩过一次的石子的序号之和。
题解：根据裴蜀定理每个青蛙可以跳到的最小石子编号为 gcd(xi,m) = bi，所有小于 m 的 bi 的倍数都是可以到达的石头。显然所有 bi 都为 m 的因子，标记 m 中所有能到达的因子，进行容斥，比如因子2、3、6都可以到达，计算 2 和 3 的倍数的时候 6 重复算了 1 次，那么可以在计算 2 和 3 的时候标记他们的倍数已经计算了 1 次，然后每个因子的贡献是 num1 - num2。详见代码~
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 #define ull unsigned long long 5 #define mst(a,b) memset((a),(b),sizeof(a)) 6 #define pii pair<int,int> 7 #define pi acos(-1) 8 #define pb push_back 9 const double eps = 1e-6; 10 const int INF = 0x3f3f3f3f; 11 const int MAXN = 1e5 + 10; 12 vector<int>vec; 13 int num1[MAXN], num2[MAXN]; 14 15 void init(int m) { 16 mst(num1, 0); 17 mst(num2, 0); 18 vec.clear(); 19 for(int i = 1; i <= sqrt(m); i++) { 20 if(m % i == 0) { 21 vec.pb(i); 22 if(i != m / i) 23 vec.pb(m / i); 24 } 25 } 26 sort(vec.begin(), vec.end()); 27 } 28 29 ll cal(int a1, int n) { 30 return (ll)n * (ll)(n + 1) / 2 * (ll)a1; 31 } 32 33 int main() { 34 #ifdef local 35 freopen("data.txt", "r", stdin); 36 #endif 37 int cas = 1; 38 int t; 39 scanf("%d", &t); 40 while(t--) { 41 int n, m; 42 scanf("%d%d", &n, &m); 43 init(m); 44 for(int i = 0; i < n; i++) { 45 int x; 46 scanf("%d", &x); 47 int temp = __gcd(x, m); 48 int pos = lower_bound(vec.begin(), vec.end(), temp) - vec.begin(); 49 num1[pos] = 1; 50 } 51 for(int i = 0; i < vec.size(); i++) { 52 if(!num1[i]) continue; 53 for(int j = i + 1; j < vec.size(); j++) 54 if(num1[j] == 0 && vec[j] % vec[i] == 0) num1[j] = 1; 55 } 56 ll ans = 0; 57 for(int i = 0; i < vec.size(); i++) { 58 int num = num1[i] - num2[i]; 59 ans = ans + cal(vec[i], m / vec[i] - 1) * num; 60 for(int j = i; j < vec.size(); j++) 61 if(vec[j] % vec[i] == 0) num2[j] += num; 62 } 63 printf("Case #%d: %lld ", cas++, ans); 64 } 65 return 0; 66 }