JZOJ 5843.B

f(x)f(x) 表示选择至少一个序列,在每个被选择的序列选择一个元素,它们的 gcd=x\gcd = x 的方案数。(式子太长了不写了)
根据反演套路,设 F(x)=xdf(d)=i=1n(j=1m[xai,j]+1)1F(x) = \sum\limits_{x | d} f(d) = \prod\limits_{i = 1}^n (\sum\limits_{j = 1}^m [x | a_{i,j}] + 1) - 1
加一是当前序列不选,减一是剔除没有选择任何序列的情况。

cnti,x=j=1m[xai,j]cnt_{i,x} = \sum\limits_{j = 1}^m [x | a_{i,j}]
limlim 表示所有元素的最大值,
于是有

把枚举的东西换成 dd,有

于是这题就这样了。
线性筛 φ\varphi,预处理 cntcnt 数组(根据套路,不要枚举因子而是枚举倍数)。
也可以预处理 sumx=i=1n(cnti,x+1)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
#include <cstdio>
#include <algorithm>
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);
}