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