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;
}