Frogs HDU - 5514 （容斥原理，）

题意：

有一堆青蛙，一开始都在0点，然后有一堆圈成一圈的石子，石子的编号是从0-m-1的

然后青蛙只能顺时针跳，每个青蛙可以一次跳a[i]格，然后所有青蛙都这样一直跳下去

然后问你，这些青蛙踩过的石子的编号和是多少？

思路：

 

首先，对于第i只青蛙，他跳过的格子，一定是k*gcd(a[i],m)这种的

由于m 较大，所以我们找m的因子来做，m的因子一定也属于 gcd(a[i],m);

m 的因子也有可能存在倍数关系，所以我们需要用到容斥原理。

我们先把m 的因子找出来，然后从小到大排序，如果m的因子是 最大公约数的倍数，那么我们在这个因子的下标上

打上一个标记。说明这个因子可以用到。

我么在设另外一个数组，num ，表示这个因子用了几次，如果大于一次，那么说明多用了，我们就需要减去这个因子所

产生的结果。

一开始，，所有数都没有用到过，所以 num 应该都是 0；

我们用了一个因子之后，如果后面的有用的因子是当前因子的倍数，那么后面的因子的num 就要加上 1 ；

if（vis[i] == num[i]） 说明在计算之前因子的时候，把这个因子计算过了，不需要用了。当前因子是之前因子的倍数，如果在用这个因子，会计算重复。

if (vis[i] != num[i]) 说明这个因子有可能被访问了，有可能没有被访问。要看这两个数的差值。

比如说，m 是 24， 我们有 2 4 6 8 这几个有用的因子，

我们先做2

之后我们就标记了 4， 6 ，8  因为做2 的时候就把 4 6 8 做完了，之后就不需要重复做了，

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define mem(x,v) memset(x,v,sizeof(x))
using namespace std;
const int N = 10005;
typedef long long LL;
int vis[N],num[N];
int p[N];
int n,m,k;
int gcd(int a, int b){
	if (b == 0) return a; else return gcd(b, a % b);
}

LL init(){
	mem(vis,0);
	mem(num,0);
	scanf("%d%d",&n,&m);
	k = 0;
	for (int i = 1; i * i <= m; i++){ //筛因子
		if (m % i == 0) {
			p[k++] = i;
			if (i * i != m) p[k++] = m / i;
		}
	}
	sort(p,p+k);
	for (int i = 0; i < n; i++){
		int x;
		scanf("%d",&x);
		x = gcd(x,m);
		for (int j = 0; j < k; j++)
			if (p[j] % x == 0) vis[j] = 1; // 找有用的因子，赋值为1；
	}
	LL ans = 0;
	for (int i = 0; i < k; i++){
		if (vis[i] != num[i]){ //看看当前的因子有没有被用过。
			int t = (m - 1) / p[i];
			ans += (LL)(t+1)*t/2*p[i]*(vis[i]-num[i]);
			t = vis[i] - num[i];
			for (int j = i; j < k; j++)
				if (p[j] % p[i] == 0) //找是当前因子的倍数，把次数加1，防止重复运算。
				num[j] += t;
		}
	}
    return ans;

}
int main(){
	int T,tt = 1;
	cin>>T;
	while(T--){
		LL ans = init();
		printf("Case #%d: %I64d\n",tt++,ans);
	}
	return 0;
}