这题很容易转化到一个容斥计数问题。而用指数复杂度的枚举计数法显然会挂，只能考虑别的方法。
首先将a[i]用gcd(a[i], m)替换，排序去重后得到一组m的约数，而m不超过1e9，因此m的所有约数最多在1000左右。
假设数组a只含有2，3两个元素，那么显然答案应该是f(2) + f(3) - f(6)，f(i)表示只有i的情况下的答案。
2和3的系数是1，6的系数是-1，其余系数为0。
根据容斥原理：对于某个特定的约数，若存在数组a的一个子集其lcm为该约数，那么若集合元素个数为偶数，贡献-1，若为奇数，贡献1。
而最终的答案一定由所有约数合成，其系数取值{-1，0，1}。
因此我们考虑数组a的前m个数，其对应的系数分布是可以确定的。
加入第m+1个数时，显然新的集合必然由原集合的子集并上新元素得到，分别考虑m的所有约数k，其对应的系数为op(k)
若op(k)为-1，则说明偶数子集的个数比奇数子集的个数多1，若我们添如新元素x，则恰好使得奇数子集个数比偶数多1，但此时贡献
不是对k的，而是对lcm(k, x)，用公式表示就是：
op(lcm(k, x)) += op(k) * (-1).
其余情形类似。
最终答案是ans = sigma(op(i) * f(i)), i | m.
这样我们只需最多进行1000次遍历就可使得元素个数加一，总复杂度约为O(1e6)。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <ctime>
#include <cassert>
#define lson (u << 1)
#define rson (u << 1 | 1)
#define cls(i, j) memset(i, j, sizeof i)
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
typedef __int64 ll;
const double eps = 1e-;
const double pi = acos(-1.0);
const int maxn = 1e4 + ;
const int maxm = 4e4 + ;
const int inf = 0x3f3f3f3f;
const ll linf = 0x3fffffffffffffff;
const ll mod = 1e9 + ; map<ll, int> mapi;
int n;
ll a[maxn], m;
int prime[maxm], k;
bool vis[maxm];
ll fact[maxn], nf;
int cnt[maxn];
ll table[maxn], nt;
int op[maxn];
int op1[maxn];
ll ans; ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b); } void init(){
cls(vis, );
k = ;
for(int i = ; i < maxm; i++){
if(vis[i]) continue;
prime[k++] = i;
for(int j = i * ; j < maxm; j += i) vis[j] = ;
}
} void dfs(int next, ll num){
if(next >= nf){
table[nt++] = num;
mapi[num] = nt - ;
return;
}
ll tem = num;
for(int i = ; i <= cnt[next]; i++){
dfs(next + , tem);
tem *= fact[next];
}
} ll f(ll num){
ll tem = (m - ) / num;
return tem * (tem + ) / * num;
} void factorize(){
nf = ;
ll m1 = m;
int mid = (int)sqrt(m);
for(int i = ; prime[i] <= mid; i++){
if(m % prime[i]) continue;
fact[nf++] = prime[i];
cnt[nf - ] = ;
while(m % prime[i] == ) ++cnt[nf - ], m /= prime[i];
mid = (int)sqrt(m);
}
if(m != ) fact[nf++] = m, cnt[nf - ] = ;
m = m1;
} ll solve(){
mapi.clear();
int n1 = ;
for(int i = ; i < n; i++){
ll tem = a[i] % m;
if(!tem) continue;
a[n1++] = gcd(m, tem);
}
n = n1;
sort(a, a + n);
n = unique(a, a + n) - a;
cls(vis, );
for(int i = ; i < n; i++){
for(int j = i + ; j < n; j++){
if(a[i] % a[j] == ) vis[i] = ;
else if(a[j] % a[i] == ) vis[j] = ;
}
}
n1 = ;
for(int i = ; i < n; i++) if(!vis[i]) a[n1++] = a[i];
n = n1;
sort(a, a + n);
factorize();
nt = ;
dfs(, );
cls(op, );
ans = ;
for(int i = ; i < n; i++){
cls(op1, );
for(int j = ; j < nt; j++){
ll tem = a[i] / gcd(a[i], table[j]) * table[j];
if(tem >= m) continue;
op1[mapi[tem]] += -op[j];
}
++op1[mapi[a[i]]];
for(int j = ; j < nt; j++) op[j] += op1[j];
}
// for(int i = 0; i < nt; i++) printf("%d ", op[i]);
// puts("");
for(int i = ; i < nt; i++) ans += op[i] * f(table[i]);
return ans;
} int main(){
// freopen("in.txt", "r", stdin);
int T, kase = ;
init();
scanf("%d", &T);
while(T--){
scanf("%d%I64d", &n, &m);
for(int i = ; i < n; i++) scanf("%I64d", &a[i]);
ll ans = solve();
printf("Case #%d: %I64d\n", ++kase, ans);
}
return ;
}