Description：

给定 $ n $ 个正整数序列 $a_1,a_2,\dots,a_n$ ，每个序列长度为 $ m$ 。 选择至少 $ 1 $ 个序列，在每个被选择的序列中选择一个元素，求出所有被选择的元素的 $\gcd$ ，求所有方案的结果之和，

$1\leqslant n\leqslant 20,1\leqslant m\leqslant 10^5,1\leqslant a_i\leqslant10^5$

Solution：

既然 $a_i$ 这么小，可以对每一行开一个桶记录一下每个权值的出现次数，然后再 $O(n\ 10^5\ln 10^5)$ 得把每个数的倍数累加到这个数上来，这样枚举每个数作为 $\gcd$ ，那么在每个序列中都可以选它的倍数，这样就把 $cnt[k][i]+1$ 累乘起来即可，加一是因为可以不选，最后还要减一，是因为减掉一个都不选的情况，发现有的 $\gcd$ 可能其实是当前枚举的数的倍数，所以再均摊 $O(n\ln n)$ 的复杂度内减掉它的倍数的值即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int read()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,m;

#define MAXN 21

#define MAXM 100010

int a[MAXN][MAXM];

int cnt[MAXN][MAXM];

#define MAX 100000

int ans[MAX];

#define MOD 1000000007

int main()

{

	freopen("b.in","r",stdin);

	freopen("b.out","w",stdout);

	int res = 0;

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)

		for(int j = 1;j <= m;++j)

			a[i][j] = read();

	for(int i = 1;i <= n;++i)

		for(int j = 1;j <= m;++j)

			cnt[i][a[i][j]] = (cnt[i][a[i][j]] + 1) % MOD;

	for(int k = 1;k <= n;++k)

		for(int i = 1;i <= MAX;++i)

			for(int j = i + i;j <= MAX;j += i)

				cnt[k][i] = (cnt[k][i] + cnt[k][j]) % MOD;

	for(int i = MAX;i >= 1;--i)

	{

		ans[i] = 1;

		for(int k = 1;k <= n;++k)

			ans[i] = 1ll * ans[i] * (cnt[k][i] + 1) % MOD;

		for(int j = i + i;j <= MAX;j += i)

			ans[i] = (ans[i] - ans[j] + MOD) % MOD;

		ans[i] = (ans[i] - 1 + MOD) % MOD;

	}

	for(int i = 1;i <= MAX;++i)

		res = (res + 1ll * i * ans[i] % MOD) % MOD;

	cout << res << endl;

	fclose(stdin);

	fclose(stdout);

	return 0;

}