题目链接 : http://acm.hdu.edu.cn/showproblem.php?pid=5514
题意 :
有m个石子围成一圈, 有n只青蛙从跳石子, 都从0号石子开始, 每只能越过a[i]个石子
问所有被至少踩过一次的石子的序号之和
思路 :
不难发现, 从0开始, 每次越过a[i]个石子, 那么gcd(a[i], m)的倍数都能被经过
石子 k * (gcd(a[i], m)) < m 的都被算入
但如果按单独每个a[i]来计算对答案的贡献, 肯定会有重复, 重复部分就是lcm(a[i], a[j])的倍数
这里要用容斥的思想解决
第一次正式接触容斥, 但其实已经有很多地方用过这种思想了
比如二维树状数组求面积, 求一个范围内能整除若干个数的个数, 还有某些概率计算
这道题中, 考虑每个gcd(a[i], m)的贡献时
首先 x = gcd(a[i], m) 一定是m的因子, x的贡献是 (m / x) * (m / x - 1) * / 2 * x
因为Sum(k * x) (1 <= k < m / x), 提取x为公因子, k就是一个等差数列求和
此时若有 y = gcd(a[j], m), y % x == 0, 则要减去一次y产生的贡献
所以解法是, 先用处理出所有m的因子, 储存在一个数组d中
对每个a[i], 都算出x = gcd(a[i], m), 遍历m的因子,
若d[i] % m == 0, 就将这个因子的贡献标记为1, vis[i] = 1, 表示这个因子应该做贡献
用一个数组记录每个因子做过的贡献, 一开始全为0
再遍历m的因子, 如果当前这个因子应该做的贡献和已经做的贡献不等, 补上贡献的次数是vis[i] - num[i]
所以套用计算贡献的公式, 当前因子x做的贡献为(m / x) * (m / x - 1) * / 2 * x * (vis[i] - num[i])
这时就要用容斥了, 这些因子中, 如果有y能整除x, x进行贡献的同时, 因子y也同时被贡献了vis[i] - num[i]次
那么对应因子y的num[j]就要加上vis[i] - num[i]
如果出现了vis[i] - num[i] < 0的情况, 说明这个因子被多贡献了, 减去相应次数的贡献即可
重现没有做出来, 代码是参考了网上大牛的
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; const int MAXN = 1e4+10; int a[MAXN]; int d[MAXN]; int vis[MAXN]; int num[MAXN]; int GCD(int a, int b) { int r = a % b; while(r) { a = b; b = r; r = a % b; } return b; } bool cmp(int a, int b) { return a < b; } void Init() { memset(vis, 0, sizeof(vis)); memset(num, 0, sizeof(num)); } int main() { int t; int n, m; scanf("%d", &t); for(int cas = 1; cas <= t; cas++) { Init(); scanf("%d %d", &n, &m); int cnt = 0; for(int i = 1; i * i <= m; i++) { if(m % i == 0) { d[cnt++] = i; if(i * i != m) { d[cnt++] = m / i; } } } sort(d, d+cnt, cmp); for(int i = 0; i < n; i++) { scanf("%d", &a[i]); a[i] = GCD(a[i], m); for(int j = 0; j < cnt; j++) { if(d[j] % a[i] == 0) { vis[j] = 1; } } } LL ans = 0; vis[cnt-1] = 0; for(int i = 0; i < cnt; i++) { if(vis[i] != num[i]) { LL temp = m / d[i]; ans += temp * (temp - 1) / 2 * d[i] * (vis[i] - num[i]); for(int j = i + 1; j < cnt; j++) { if(d[j] % d[i] == 0) { num[j] += vis[i] - num[i]; } } } } printf("Case #%d: %I64d\n", cas, ans); } return 0; }
原文：http://www.cnblogs.com/Quinte/p/4932471.html
