hdu5514Frogs（容斥原理）

显然，第 i 只青蛙能跳过的石头的 id = k*gcd(a[i],m)。所以题目就是相当于求 0 ~ m - 1 这些数中至少是一个 a[i] (a[i]|m) 的倍数。

0 ~ m - 1 这些数中是 d (d|m) 的倍数的和为

d * m/d * (m/d - 1) / 2 。

但是，这样计算必然会重复。

先把 m 的因数求出来，最多不多于300个，再把是 a[i] 倍数的因数标记（我们要保证它们只算一遍！！！）。从小枚举 m 的因数，把 m 未枚举到的因数中多算的记到 num[j] 里面去，这样计算的时候改为

d * m/d * (m/d - 1) / 2 * (vis[j]-num[j]) 就能得到正确答案。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <stack>
#include <vector>
#include <cstring>
#include <queue>
#define msc(X) memset(X,-1,sizeof(X))
#define ms(X) memset(X,0,sizeof(X))
typedef long long LL;
using namespace std;

const int maxn=+;
int vis[maxn],num[maxn],fac[maxn],cnt;
int gcd(int a,int b)
{return b?gcd(b,a%b):a;} 
int main(int argc, char const *argv[])
{
    int t,ti=;
    scanf("%d",&t);
    while(++ti<=t)
    {
        int n,m;LL ans=;
        scanf("%d%d",&n,&m);
        cnt=;
        ms(vis);
        ms(num);
        for(int i=;(LL)i*i<=m;i++)
            if(m%i==)
            {
                fac[cnt++]=i;
                if(i*i<m) fac[cnt++]=m/i;
            }
        sort(fac,fac+cnt);
        --cnt;
        for(int i=;i<n;i++)
        {
            int x;
            scanf("%d",&x);
            x=gcd(x,m);
            for(int j=;j<cnt;j++)
                if(fac[j]%x==) vis[j]=;
        }
        for(int i=;i<cnt;i++)
            if(vis[i]&&vis[i]!=num[i])
            {
                ans+=(LL)fac[i]*(m/fac[i])*(m/fac[i]-)/*(vis[i]-num[i]);
                for(int j=i+;j<cnt;j++)
                    if(fac[j]%fac[i]==)
                        num[j]+=vis[i]-num[i];
            }
        printf("Case #%d: %lld\n",ti,ans );
    }
    return ;
}