题意：

n个青蛙，m个点，编号为0到m-1

每个青蛙的跳跃的距离为xi，起点都是0，问：m个点中，所有可以到达的编号的和是多少


分析样例：

先选个简单的：

2 12
9 10
（9）：产生的所有数是：3，6，9

（10）：产生的所有数是：2，4，6，8，10

发现了GCD：（9，12）=3，（10，12）=2

而且和是与GCD，m有关的一个式子

那么6多了，如何处理呢？容斥原理减掉

选个最麻烦的吧：

9 96
81 40 48 32 64 16 96 42 72
（81，96）=3，（40，96）=8，（48，96）=48，（32，96）=32，（64，96）=32，（16，96）=16，（96，96）=96，（42，96）=6，（72，96）=24

可以看到，除了3和8之外，其他的GCD都是3或者8的倍数（都可以扔掉，因为产生的数都会是重复的）

那么，根据刚才说的容斥：我们只需要算上3的，算上8的，减去24的（重复了）


这样算来，我们得到了一个好的做法（错误的做法）：

把所有的GCD列出来，排个序，然后如果有倍数情况的扔掉，然后用容斥原理来搞一发！

（当然会有个小的剪枝：如果最小的GCD是1，那么表示所有的值都会取得到，提前输出m*（m-1）/2即可）

容斥原理的经典写法：状态压缩

假设有tot个GCD，那么maxnum=(1<<tot)

状态值从0枚举到maxnum-1，然后如果状态值st的二进制表示位上有奇数个1，说明这个值要加；否则，这个值要减

代码如下：wrong answer


为什么这么写不对呢？？因为，我们在容斥的时候，会发现，需要把某些GCD值乘起来，是不是会超过m呢？

如果是连续的多个素数，2，3，5，7，11，13，17，19，23，取最小的连续9个素数

得到Hack数据1：

9 223092870
2 3 5 7 11 13 17 19 23

可以计算得：现在的m刚好是这9个数相乘，不会越界

那么，我们怎么样构造一组可以越界的呢？很简单，这些素数两两相乘！得到Hack数据2：

10 223092870
6 10 14 22 26 34 38 46 15 21

这样，这些数都满足GCD的条件，也相互不是倍数和约数的关系，但是乘起来是越界的，我们的程序没有处理到这一点


于是：我们必须采取另外的容斥姿势：从小到大，来枚举m的所有可能因子（首先把因子打表打到数组里）

然后还是计算每个青蛙跳跃距离和m的GCD值，然后根据GCD值，来看看GCD可以产生出来哪些因子，给予标记

然后定义num数组

当num数组不为1时，说明当前的容斥不对（那么我们需要加加减减来抵消掉其他的运算）

但是在这样抵消的时候，当前枚举值的倍数也被相应的影响了这么多的次数

所以，这是用另一种思路写的容斥，代码如下：

#include<bits/stdc++.h>
using namespace std;

#define LL __int64
const int maxn=1e5+50;

int p[maxn],cnt;
int vis[maxn];
int num[maxn];

LL gcd(LL x,LL y){
    return x%y==0?y:gcd(y,x%y);
}

int main(){
    //freopen("input.txt","r",stdin);
    int t,n,m,x;
    scanf("%d",&t);
    for(int Case=1;Case<=t;Case++){
        memset(vis,0,sizeof(vis));
        memset(num,0,sizeof(num));
        cnt=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i*i<=m;i++)
            if (m%i==0){
                p[cnt++]=i;
                if (i*i!=m) p[cnt++]=m/i;
            }
        sort(p,p+cnt);
        //for(int i=0;i<cnt;i++) printf("%d%c",p[i],i==cnt-1?'\n':' ');
        for(int i=1;i<=n;i++){
            scanf("%d",&x);
            x=gcd(x,m);
            for(int j=0;j<cnt;j++)
                if (p[j]%x==0) vis[j]=1;
        }
        vis[cnt-1]=0;
        LL ans=0;
        for(int i=0;i<cnt;i++)
        if (vis[i]!=num[i]){
            LL temp=m/p[i];
            ans+=temp*(temp-1)/2*p[i]*(vis[i]-num[i]);
            int change=vis[i]-num[i];
            for(int j=i;j<cnt;j++)
                if (p[j]%p[i]==0)
                    num[j]+=change;
        }
        printf("Case #%d: %I64d\n",Case,ans);
    }
    return 0;
}