题目概述

有一棵树，如果 $w_i|w_j$ 且 $j$ 是 $i$ 的祖先那么 $j$ 可以直接到达 $i$ ，问从第一个点到所有点的方案数。

解题报告

$O(n^2)$ DP很显然，考虑优化。如果把每个数素因子的幂拿下来组成向量，那么 $i|j$ 需要满足 $j$ 每一维都大于等于 $i$ ，就变成了一个求超集的问题。因子之间的子集超集我们可以存下所有因子然后建边来方便的转移。

然而 $10^{18}$ 内因子最多有 $2^{16}$ 个，不可能直接做，上套路！枚举子集其实可以拆成两半做，参考UOJ300吉夫特 。先用PR把 $w_1$ 拆分，然后我们把 $w_1$ 的因子尽量拆成两半，一半只由前若干个素数构成，另一半由剩下的素数构成。

这样处理之后两半因子的个数为 $O(256)$ ，就可以建边了。之后记录 $sum_{i,j}$ 表示前一半为 $i$ ，后一半为 $j$ 的超集的总和，每次求 $i$ 的超集只需要先把 $i$ 拆成左右两半 $L,R$ ，然后 $\sum_{L|i}sum_{i,R}$ 就是答案。

示例程序

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long LL;typedef long double DB;
const int maxn=100000,maxp=65536,maxs=1000,MOD=1e9+7,prime[]={2,3,5,7,11,13,17,19};

int n,P,num[maxp+5],S;LL w[maxn+5],p[maxp+5];int si[2];LL D[2][maxs+5];int f[maxn+5],sum[maxs+5][maxs+5];
int E,lnk[3][maxn+5],nxt[(maxn<<1)+maxs*maxs+5],son[(maxn<<1)+maxs*maxs+5];

inline LL Mul(LL x,LL y,LL MOD) {return ((x*y-(LL)((DB)x/MOD*y)*MOD)%MOD+MOD)%MOD;}
inline LL Pow(LL w,LL b,LL MOD) {LL s=1;for (;b;b>>=1,w=Mul(w,w,MOD)) if (b&1) s=Mul(s,w,MOD);return s;}
inline bool MR(LL n){
    for (int i=0;i<8;i++) if (!(n%prime[i])) return n==prime[i];
    for (int t=1;t<=8;t++){
        LL x;int k=0;for (x=n-1;!(x&1);x>>=1) k++;x=Pow(rand()%(n-2)+2,x,n);if (x==1) continue;LL s;
        for (s=Mul(x,x,n);k;k--,x=s,s=Mul(x,x,n)) if (s==1) {if (x<n-1) return false;break;}if (s>1) return false;
    }return true;
}
#define Abs(x) ((x)<0?-(x):(x))
LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;}
inline void AMOD(LL &x,LL tem,LL MOD) {if ((x+=tem)>=MOD) x-=MOD;}
inline LL FindD(LL n){
    LL x=rand()%(n-1)+1,y,r=rand()%(n-1)+1;
    for (int i=1,k=1;;i++){
        AMOD(x=Mul(x,x,n),r,n-1);x++;if (x==y) return -1;LL GCD=gcd(Abs(x-y),n);
        if (GCD>1) return GCD;if (i==k) y=x,k<<=1;
    }
}
void PR(LL n){
    if (n==1) return;if (MR(n)) {p[++P]=n;return;}
    LL D;while ((D=FindD(n))<0);PR(D);PR(n/D);
}
#define Add(ID,x,y) (son[++E]=(y),nxt[E]=lnk[ID][x],lnk[ID][x]=E)
inline int Find(int ID,LL x){int L=1,R=si[ID];
    for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
        D[ID][mid]<=x?L=mid+1:R=mid-1;return R;
}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
void Dfs(int x,int pre=0){
    LL now=w[x];for (int i=1;i<=S;i++) while (!(now%p[i])) now/=p[i];
    int L=Find(0,w[x]/now),R=Find(1,now);f[x]=x==1;
    for (int j=lnk[1][L];j;j=nxt[j]) AMOD(f[x],sum[son[j]][R]);
    for (int j=lnk[2][R];j;j=nxt[j]) AMOD(sum[L][son[j]],f[x]);
    for (int j=lnk[0][x];j;j=nxt[j]) if (son[j]!=pre) Dfs(son[j],x);
    for (int j=lnk[2][R];j;j=nxt[j]) AMOD(sum[L][son[j]],MOD-f[x]);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);for (int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),Add(0,x,y),Add(0,y,x);
    for (int i=1;i<=n;i++) scanf("%lld",&w[i]);PR(w[1]);sort(p+1,p+1+P);P=0;
    for (int i=1,j;p[i];i=j) {for (j=i+1;p[j]&&p[i]==p[j];j++);p[++P]=p[i];num[P]=j-i;}
    int tot=1;for (int i=1;i<=P;i++) tot*=num[i]+1;for (int t=1;t*t<tot;S++) t*=num[S+1]+1;
    for (int i=1,s=D[0][si[0]=1]=1;i<=S;i++,s=si[0])
        for (int j=1;j<=s;j++) for (LL k=1,w=p[i];k<=num[i];w*=p[i],k++) D[0][++si[0]]=D[0][j]*w;
    for (int i=S+1,s=D[1][si[1]=1]=1;i<=P;i++,s=si[1])
        for (int j=1;j<=s;j++) for (LL k=1,w=p[i];k<=num[i];w*=p[i],k++) D[1][++si[1]]=D[1][j]*w;
    sort(D[0]+1,D[0]+1+si[0]);sort(D[1]+1,D[1]+1+si[1]);
    for (int i=1;i<=si[0];i++) for (int j=i;j<=si[0];j++) if (!(D[0][j]%D[0][i])) Add(1,i,j);
    for (int i=1;i<=si[1];i++) for (int j=i;j<=si[1];j++) if (!(D[1][j]%D[1][i])) Add(2,j,i);
    Dfs(1);for (int i=1;i<=n;i++) printf("%d\n",f[i]);return 0;
}