Description：

求一张带权图的所有生成树的边权的最大公约数之和，对 $10^9+7$ 取模。

$1\leqslant n\leqslant 60,1\leqslant m\leqslant 3000,1\leqslant 10^6$

Solution：

肯定是枚举 $\gcd$ ，然后统计答案为 $g$ 的方案数 $f(d)$ ，最后的答案就是 $\sum g\times f(g)$ 。

但是显然这样是不好求的，那么再按照套路，设 $F(d)$ 表示 $\gcd$ 是 $d$ 的倍数的数，即： $$ F(n)=\sum_{n|d}f(d) $$ 那么 $F(n)$ 是很好求的，我们可以把所有 $n$ 的倍数的边拿出来做矩阵树定理就可以了。

然后根据莫比乌斯反演的第二种形式可以得到： $$ f(d)=\sum_{n|d}\mu(\frac d n)F(d) $$

$$ ans=\sum_{n=1}^wF(n)\sum_{d|n}d\mu(\frac n d) $$

右面那个可以狄利克雷卷积 $O(n\ln n)$ 算。

最后再加一个有理有据的常数优化，就是统计一下每个数字作为因数的出现次数，如果小于 $n-1$ 答案一定为 $0$ ，会发现实际上每个数字的因数在 $n$ 很大的时候远远不到 $n\sqrt n$ ，而且因数有很多重叠，所以就能过了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 61

#define MAXM 3010

struct edges

{

	int u,v,w;

}es[MAXM];

#define MAX 1000010

int cnt[MAX];

bool isprime[MAX];

int prime[MAX],tot = 0;

int mu[MAX];

#define MOD 1000000007

int power(int a,int b)

{

	int res = 1;

	while(b > 0)

	{

		if(b & 1)res = 1ll * res * a % MOD;

		a = 1ll * a * a % MOD;

		b = b >> 1;

	}

	return res;

}

int g[MAXN][MAXN];

int matrixtree(int k)

{

	memset(g,0,sizeof(g));

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

	{

		if(es[i].w % k == 0)

		{

			++g[es[i].u][es[i].u];++g[es[i].v][es[i].v];

			--g[es[i].u][es[i].v];--g[es[i].v][es[i].u];

		}

	}

	int s = n - 1;

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

	{

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

		{

			g[i][j] = (g[i][j] + MOD) % MOD;

		}

	}

	int tag = 1;

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

	{

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

		{

			if(g[j][i] != 0)

			{

				for(int l = i;l <= s;++l)swap(g[i][l],g[j][l]);

				if(j != i)tag *= -1;

				break;

			}

		}

		if(g[i][i] == 0)return 0;

		for(int j = i + 1;j <= s;++j)

		{

			int ratio = 1ll * g[j][i] * power(g[i][i],MOD - 2) % MOD;

			for(int l = i;l <= s;++l)

			{

				g[j][l] = (g[j][l] - 1ll * ratio * g[i][l] % MOD + MOD) % MOD;

			}

		}

	}

	int res = 1;

	for(int i = 1;i <= s;++i)res = 1ll * res * g[i][i] % MOD;

	res = (res * tag + MOD) % MOD;

	return res;

}

int main()

{

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

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

	{

		scanf("%d%d%d",&es[i].u,&es[i].v,&es[i].w);

	}

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

	{

		int v = es[i].w;

		for(int j = 1;j * j <= v;++j)

		{

			if(v % j == 0)

			{

				++cnt[j];

				if(j * j != v)++cnt[v / j];

			}

		}

	}

	for(int i = 2;i < MAX;++i)isprime[i] = true;

	mu[1] = 1;

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

	{

		if(isprime[i])prime[++tot] = i,mu[i] = -1;

		for(int j = 1;j <= tot && i * prime[j] < MAX;++j)

		{

			isprime[i * prime[j]] = false;

			if(i % prime[j] == 0)

			{

				mu[i * prime[j]] = 0;

				break;

			}

			else mu[i * prime[j]] = -mu[i];

		}

	}

	int ans = 0;

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

	{

		if(cnt[i] >= n - 1)

		{

			int sum = 0;

			for(int d = 1;d * d <= i;++d)

			{

				if(i % d == 0)

				{

					sum += d * mu[i / d];

					if(d * d != i)sum += i / d * mu[d];

				}

			}

			ans = (ans + 1ll * sum * matrixtree(i) % MOD + MOD) % MOD;

		}

	}

	cout << ans << endl;

	return 0;

}