JZOJ 5843 B

设 f(x) 表示选择至少一个序列，在每个被选择的序列选择一个元素，它们的 gcd=x 的方案数。（式子太长了不写了）
根据反演套路，设 F(x)=∑x|df(d)=n∏i=1(m∑j=1[x|ai,j]+1)−1。
加一是当前序列不选，减一是剔除没有选择任何序列的情况。

设 cnti,x=m∑j=1[x|ai,j]；
设 lim 表示所有元素的最大值，
于是有 lim∑i=1if(i)=lim∑i=1i∑i|dF(d)μ(di)=lim∑i=1i∑i|dμ(di)(n∏j=1(cntj,d+1)−1)

把枚举的东西换成 d，有 lim∑i=1i∑i|dμ(di)(n∏j=1(cntj,d+1)−1)=lim∑d=1∑i|diμ(di)(n∏j=1(cntj,d+1)−1)=lim∑d=1φ(d)(n∏j=1(cntj,d+1)−1)

于是这题就这样了。
线性筛 φ，预处理 cnt 数组（根据套路，不要枚举因子而是枚举倍数）。
也可以预处理 sumx=n∏i=1(cnti,x+1)，不过没啥用反正只用一次不如暴力（

代码：

#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);
}