设 \(f(x)\) 表示选择至少一个序列，在每个被选择的序列选择一个元素，它们的 \(\gcd = x\) 的方案数。（式子太长了不写了）
根据反演套路，设 \(F(x) = \sum\limits_{x | d} f(d) = \prod\limits_{i = 1}^n (\sum\limits_{j = 1}^m [x | a_{i,j}] + 1) - 1\)。
加一是当前序列不选，减一是剔除没有选择任何序列的情况。
设 \(cnt_{i,x} = \sum\limits_{j = 1}^m [x | a_{i,j}]\)；
设 \(lim\) 表示所有元素的最大值，
于是有 \[\begin{align*}
& \sum\limits_{i = 1}^{lim} i f(i) \\
= & \sum\limits_{i = 1}^{lim} i \sum\limits_{i | d} F(d) \mu(\dfrac d i) \\
= & \sum\limits_{i = 1}^{lim} i \sum\limits_{i | d} \mu(\dfrac d i) (\prod\limits_{j = 1}^n (cnt_{j,d} + 1) - 1)
\end{align*}\]
把枚举的东西换成 \(d\)，有 \[\begin{align*} & \sum\limits_{i = 1}^{lim} i \sum\limits_{i | d} \mu(\dfrac d i) (\prod\limits_{j = 1}^n (cnt_{j,d} + 1) - 1) \\ = & \sum\limits_{d = 1}^{lim} \sum\limits_{i | d} i \mu(\dfrac d i) (\prod\limits_{j = 1}^n (cnt_{j,d} + 1) - 1) \\ = & \sum\limits_{d = 1}^{lim} \varphi(d) (\prod\limits_{j = 1}^n (cnt_{j,d} + 1) - 1) \end{align*}\]
于是这题就这样了。
线性筛 \(\varphi\)，预处理 \(cnt\) 数组（根据套路，不要枚举因子而是枚举倍数）。
也可以预处理 \(sum_x = \prod\limits_{i = 1}^n (cnt_{i,x} + 1)\)，不过没啥用反正只用一次不如暴力（
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
using namespace std;
const int N = 20;
const int M = 1e5;
const int C = 1e5;
const long long mod = 1e9 + 7;
int n,m,a[N + 5][M + 5],cnt[N + 5][M + 5],lim;
int vis[C + 5],prime[C + 5],p_cnt,phi[C + 5];
long long ans;
int main()
{
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
phi[1] = 1;
for(register int i = 2;i <= C;++i)
{
if(!vis[i])
prime[++p_cnt] = i,phi[i] = i - 1;
for(register int j = 1;j <= p_cnt && i * prime[j] <= C;++j)
{
vis[i * prime[j]] = 1;
if(!(i % prime[j]))
{
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
else
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
}
scanf("%d%d",&n,&m);
for(register int i = 1;i <= n;++i)
for(register int j = 1;j <= m;++j)
scanf("%d",a[i] + j),lim = max(lim,a[i][j]),++cnt[i][a[i][j]];
for(register int i = 1;i <= n;++i)
for(register int j = 1;j <= lim;++j)
for(register int k = 2;j * k <= lim;++k)
cnt[i][j] += cnt[i][j * k];
for(register int i = 1;i <= lim;++i)
{
long long prod = 1;
for(register int j = 1;j <= n;++j)
prod = prod * (cnt[j][i] + 1) % mod;
ans = (ans + (prod - 1) * phi[i]) % mod;
}
printf("%lld\n",ans);
}