题目
正解
大套路题。
看到之后是个人都知道要先反演一下推推式子：
（为了方便表示，题目中的(w_{e_i})直接用(e_i)表示了）
[sum_T (sum e_i)(gcd e_i) \
=sum_T (sum e_i)sum_{d|(gcd e_i)} phi(d) \
=sum_d phi(d) sum_{T,d|e_i}sum e_i]
我们要求的是后面的那个东西。用人话说就是：所有边权为(d)的倍数的边，组成的生成树的边权和之和。
然后很容易想到矩阵树。但是由于每个生成树的贡献是(sum e_i)而不是(prod e_i)，所以要用到一个大套路：
边权为(e_i)的边，丢到基尔霍夫矩阵中的边权为(1+e_ix)。矩阵树定理搞完之后求一次项系数即是答案。
可以这么理解：对于某条边，如果计算它的贡献，就是要计算它的边权以及生成树包含这条边的方案数。
计算的时候保留常数项和一次项即可。至于求逆，可以手算出(a+bx)的逆元为(frac{1}{a}-frac{b}{a^2}x)。
大优化：计算之前先判断一下符合条件的边是否能组成至少一个生成树。
一个边权的因数个数最多为(144)。于是时间大概就是(O(frac{144mn^3}{n-1})=O(144n^4))
显然实际上也不可能真正达到这个时间复杂度。所以是可以过的。
代码
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cassert>
#define N 35
#define M N*N
#define MX 152505
#define mo 998244353
#define ll long long
ll qpow(ll x,ll y=mo-2){
ll r=1;
for (;y;y>>=1,x=x*x%mo)
if (y&1)
r=r*x%mo;
return r;
}
int n,m;
struct edge{
int u,v,w;
} ed[M];
int mx,p[MX],np;
bool inp[MX];
int phi[MX];
void getphi(int mx){
inp[1]=1,phi[1]=1;
for (int i=2;i<=mx;++i){
if (!inp[i]){
p[++np]=i;
phi[i]=i-1;
}
for (int j=1;j<=np && i*p[j]<=mx;++j){
inp[i*p[j]]=1;
if (i%p[j]==0){
phi[i*p[j]]=phi[i]*p[j];
break;
}
phi[i*p[j]]=phi[i]*(p[j]-1);
}
}
}
struct Po{
int x0,x1;
bool eql0(){return x0==0 && x1==0;}
Po inv(){
int m=qpow(x0);
return (Po){m%mo,(ll)(mo-x1)*m%mo*m%mo};
}
};
Po operator-(Po a){return (Po){(mo-a.x0)%mo,(mo-a.x1)%mo};}
Po operator+(Po a,Po b){return (Po){(a.x0+b.x0)%mo,(a.x1+b.x1)%mo};}
Po operator-(Po a,Po b){return (Po){(a.x0-b.x0+mo)%mo,(a.x1-b.x1+mo)%mo};}
Po operator*(Po a,Po b){return (Po){(ll)a.x0*b.x0%mo,((ll)a.x0*b.x1+(ll)a.x1*b.x0)%mo};}
Po &operator+=(Po &a,Po b){return a=a+b;}
Po &operator-=(Po &a,Po b){return a=a-b;}
Po &operator*=(Po &a,Po b){return a=a*b;}
int determinant(Po m[N][N]){
int o=1;
for (int i=1;i<n;++i){
int j=i;
for (;j<n && m[j][i].eql0();++j);
if (i!=j){
o=mo-o;
for (int k=i;k<n;++k)
swap(m[i][k],m[j][k]);
}
Po inv=-m[i][i].inv();
for (++j;j<n;++j)
if (!m[j][i].eql0()){
Po tmp=inv*m[j][i];
for (int k=i;k<n;++k)
m[j][k]+=m[i][k]*tmp;
}
}
Po r={o,0};
for (int i=1;i<n;++i)
r*=m[i][i];
return r.x1;
}
int dsu[N];
int getdsu(int x){return dsu[x]==x?x:dsu[x]=getdsu(dsu[x]);}
Po mat[N][N];
int calc(int d){
for (int i=1;i<=n;++i)
dsu[i]=i;
for (int i=1;i<=m;++i)
if (ed[i].w%d==0){
int x=getdsu(ed[i].u),y=getdsu(ed[i].v);
if (x!=y)
dsu[x]=y;
}
getdsu(1);
for (int i=2;i<=n;++i)
if (getdsu(i)!=dsu[1])
return 0;
memset(mat,0,sizeof mat);
for (int i=1;i<=m;++i)
if (ed[i].w%d==0){
int u=ed[i].u,v=ed[i].v;
Po w={1,ed[i].w};
mat[u][u]+=w,mat[v][v]+=w;
mat[u][v]-=w,mat[v][u]-=w;
}
return determinant(mat);
}
int main(){
freopen("count.in","r",stdin);
freopen("count.out","w",stdout);
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=m;++i){
scanf("%d%d%d",&ed[i].u,&ed[i].v,&ed[i].w);
mx=max(mx,ed[i].w);
}
getphi(mx);
ll ans=0;
for (int i=1;i<=mx;++i)
ans+=(ll)phi[i]*calc(i)%mo;
ans%=mo;
printf("%lld
",ans);
return 0;
}