题意：

有n只青蛙，有m块石头，编号为0～m-1，第i只青蛙每次可以跳$a_i$步，刚开始都在0，问青蛙总共可以跳到的石头之和为多少。其中$t≤20$，$1≤n≤10^4$，$1≤m≤10^9$，$1≤a_i≤10^9$。

思路：

根据裴蜀定理知，对于一个有n个点的环，每个循环节的长度为n/gcd(n, k)，k为每次走的步数。所以青蛙可以达到的石头编号肯定是$gcd(m,a_i)$的倍数。相当于真正步长为$gcd(m,a_i)$。

很容易就知道要容斥搞一搞，看到n这么大，就没有然后了…

看了题解知道原来容斥是可以搞的。

法一：容斥原理

要求$gcd(m,a_1)$,$gcd(m,a_2)$,$gcd(m,a_3)$…$gcd(m,a_n)$的倍数之和，可以利用$gcd(m,a_i)$是m的因子这个特点。

所以处理出m的因子，然后算贡献。

首先对于m以内的$gcd(m,a_i)$的倍数，标记为1，说明这些数的倍数都有可能算进答案里。然后从小到大，如果某个数的贡献（该数的倍数之和）算入了答案，那么它的倍数应该少算一次贡献，那么就把标记减1。然后每次算的时候就是标记*贡献。贡献用等差数列求和算一下就可以了。

复杂度为$O(t*1000*n)$。

一直在想这些数的lcm要怎么处理，还计数搞了好久…然而正确的思路总是明了的思想啊…

法二：欧拉函数的应用

因为可能有多只青蛙占领同一个石头的情况，所以有消除重复的办法。

比如样例一，m=12，$a_1=9$，$a_2=10$，$gcd(m,a_1)=3$，$gcd(m,a_1)=2$。可以规定每个石头i只能被步长为$gcd(m,i)$的青蛙占领。

2，10只能由步长为2的来占领；

3，9只能由步长为3的来占领；

4，8只能由步长为4的来占领；

6只能由步长为6的来占领。

算一下和，

2+10=2*(1+5)；

3+9=3*(1+3);

4+8=4*(1+2);

6=6*1。

所以如果步长为x，可以占领的石头的编号和为x*(与$\frac{m}{x}$互质的数之和)。

因为有结论小于n，且与n互质的所有数字的和是$\frac{φ(n)∗n}{2}$。

所以就可以做了。

这个方法比较难想到，特别是消除重复和m/x得到的地方。这么消除重复的方式可以学习一下。

代码：

法一：

typedef long long ll;
int a[10010],b[10010];
vector<int>v;
int num[10010];
int gcd(int a,int b)
{
    if(a<b){int temp;temp=a;a=b;b=temp;}
    if(b==0)return a;
    while(a%b){int r=a%b;a=b;b=r;}
    return b;
}
ll calc(int x)
{
    if(x%2==0)return 1ll*x/2*(x+1);
    return 1ll*(x+1)/2*x;
}
int main()
{
    int t,n,m;
    scanf("%d",&t);
    for(int kase=1;kase<=t;kase++)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)
            b[i]=gcd(m,a[i]);
        v.clear();
        for(int i=1;i*i<=m;i++)
        {
            if(m%i==0)
            {
                v.push_back(i);
                if(i!=m/i)v.push_back(m/i);
            }
        }
        sort(v.begin(),v.end());
        memset(num,0,sizeof(num));
        int len=v.size();
        for(int i=0;i<len;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(v[i]%b[j]==0)
                    num[i]=1;
            }
        }
        /*for(int i=0;i<len;i++)
            printf("%d ",v[i]);
        printf("\n");
        for(int i=0;i<len;i++)
            printf("%d ",num[i]);
        printf("\n");*/
        ll tot=0;
        for(int i=0;i<len;i++)
        {
            if(num[i]==0)continue;
            int temp=(m-1)/v[i];
            tot+=num[i]*calc(temp)*v[i];
            for(int j=i+1;j<len;j++)
            {
                if(v[j]%v[i]==0)
                    num[j]-=num[i];
            }
            /*for(int j=0;j<len;j++)
                printf("%d ",num[j]);
            printf("\n");*/
        }
        printf("Case #%d: %lld\n",kase,tot);
    }
    return 0;
}

法二：

typedef long long ll;
int a[10010],b[10010];
vector<int>v;
int num[10010];
int gcd(int a,int b)
{
    if(a<b){int temp;temp=a;a=b;b=temp;}
    if(b==0)return a;
    while(a%b){int r=a%b;a=b;b=r;}
    return b;
}
ll euler(int n)
{
    int i;
    ll res=1ll*n;
    for(i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            res=res/i*(i-1);
            while(n%i==0)
                n=n/i;
        }
    }
    if(n>1)res=res/n*(n-1);
    return res;
}
int main()
{
    int t,n,m;
    scanf("%d",&t);
    for(int kase=1;kase<=t;kase++)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)
            b[i]=gcd(m,a[i]);
        v.clear();
        for(int i=1;i*i<=m;i++)
        {
            if(m%i==0)
            {
                v.push_back(i);
                if(i!=m/i)v.push_back(m/i);
            }
        }
        memset(num,0,sizeof(num));
        ll tot=0;
        int len=v.size();
        for(int i=1;i<=n;i++)
            for(int j=0;j<len;j++)
                if(v[j]%b[i]==0)
                    num[j]=1;
        for(int i=0;i<len;i++)
        {
            if(num[i]&&v[i]!=m)
            {
                ll temp=euler(m/v[i])*m/2;
                tot+=temp;
                //printf("%d %lld\n",v[i],temp);
            }
        }
        printf("Case #%d: %lld\n",kase,tot);
    }
    return 0;
}