题意：
给你n个青蛙，起点相同都在0点，然后每个青蛙有步长ai，代表可以从当前位置跳到+ai的位置，位置是一个环，从0到m-1，所有可以有青蛙跳到的位置的下标和是多少。
思路：
首先可以观察到步长为ai的青蛙可以到达的位置是gcd(a[i],m)的倍数。 如果只有一只青蛙，我们可以直接用等差数列的公式算出答案。 现在考虑有多只青蛙的情况，会算重的地方就是它们的最小公倍数的位置。 直接用容斥原理会TLE。 考虑到所有的答案一定是m的因子，先O(sqrt(m))筛出m的因子，然后算出容斥原理公式在每个因子前的系数就好了。 至于算系数，我们可以这样考虑，在算一个因子的答案时，它还会算到其倍数的答案，我们要的是每个数恰好算一遍的答案，即初始化时系数为可以访问到的因子fac[i]他的系数应该是vis[i]=1 其后我们使用公式算的时候，每算一个fac[i]的答案，都会对其倍数因子的答案贡献加1，所以其倍数的系数应该减去该被加次数。这样就是O(tot^2)的时间复杂度，tot是因子的个数
代码：
#define debug printf
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<map>
#include<vector>
using namespace std;
typedef long long LL;
const int maxn=
10000+
100;
int kase=
0;
int a[maxn];
int ga[maxn];
int vis[maxn];
int fac[maxn];
int tot=
0;
int n,m;
int newn;
LL ans=
0;
void solve();
LL cal(
int x);
LL lcm(
int a,
int b)
{
return a/__gcd(a,b)*LL(b);
}
LL lcm(LL a,LL b)
{
return a/__gcd(a,b)*(b);
}
LL getfac(
int x);
int main()
{
int T;
scanf(
"%d",&T);
kase=
0;
while(T--){
kase++;
solve();
}
return 0;
}
void solve()
{
scanf(
"%d %d",&n,&m);
for(
int i=
0;i<n;i++){
scanf(
"%d",&a[i]);
}
for(
int i=
0;i<n;i++){
ga[i]=__gcd(a[i],m);
}
sort(ga,ga+n);
newn=unique(ga,ga+n)-ga;
printf(
"Case #%d: ",kase);
if(ga[
0]==
1){
ans=cal(
1);
printf(
"%lld\n",ans);
return;
}
getfac(m);
sort(fac,fac+tot);
memset(vis,
0,
sizeof(vis));
for(
int i=
0;i<newn;i++){
for(
int j=
0;j<tot;j++){
if(fac[j]%ga[i]==
0){
vis[j]=
1;
}
}
}
ans=
0;
for(
int i=
0;i<tot;i++){
if(vis[i]!=
0){
ans+=vis[i]*cal(fac[i]);
for(
int j=i+
1;j<tot;j++){
if(fac[j]
