CF 990 G GCD Counting

这种等于 $d$ 的题往往要化成一个比较好求的形式。。比如这个题，如果推 $=d$ 的式子最后发现点分时需要两次莫反，复杂度是 $O(n\log^3 n)$ ，但是一个比较好的思路就是求 $d$ 整除 $g(x,y)$ 的 $(x,y)$ 对数，如果设这样求出来的是 $s(x)$ ，并且我们最后要算的是 $f(x)$ 那么有：

$$s(x) = \sum_{x|d} f(d)$$

不难发现这是个狄利克雷前缀和的形式，可以卷回去，卷回去的复杂度仅仅是 $O(n\log\log n)$ 。

于是问题就简化成了求 $d$ 整除 $g(x,y)$ 的数目。

考虑点分治，当前点分的根是 $u$ ，怎么求答案。

我们假设当前已经考虑到了子树 $v$ ，之前已经找到过的所有子树与根和起来称作 $u$ 。那么我们现在需要算：

$$\sum_{x=1}^{siz[u]}\sum_{y=1}^{siz[v]} \sum_{d=1}^{2\times10^5} [d|\gcd(A[x],B[y])]$$

其中 $A$ 代表 $u$ 子树内的所有点分别到达 $u$ 的路径的 $\gcd$ ，$B$ 代表 $v$ 的，注意 $\gcd$ 运算有一个性质，你多 $\gcd$ 一遍根是没有影响的。甚至不需要反演，直接调换一下循环顺序并把 $\gcd$ 拆开

$$\sum_{d=1}^{2\times10^5} \sum_{x=1}^{siz[u]}\sum_{y=1}^{siz[v]} [d|A[x],d|B[y]]$$

我们考虑对所有数字事先筛除它们的约数，约数个数和是 $O(n\log n)$ 级别的。

然后我们对每个数字分别统计一下就好了。复杂度最多就是约数个数的最大值 $160$ ，而且多数情况下很优秀。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 200006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
ll n , m;
int A[MAXN];
int gcd( int a , int b ) {
    return !b ? a : gcd( b , a % b );
}
vector<int> divs[MAXN];
int pri[MAXN] , en;
void prewk( ) {
    for( int i = 2 ; i < MAXN ; ++ i ) {
        if( !pri[i] ) pri[++ en] = i;
        for( int j = 1 ; j <= en && i * pri[j] < MAXN ; ++ j ) {
            pri[i * pri[j]] = 1;
            if( i % pri[j] == 0 ) break;
        }
    }
    for( int i = 1 ; i < MAXN ; ++ i )
        for( int j = i ; j < MAXN ; j += i )
            divs[j].pb( i );
}
vector<int> G[MAXN];

int vis[MAXN];
int siz[MAXN] , mx[MAXN] , S , pr;
void fds( int u , int fa ) {
    siz[u] = 1; mx[u] = 0;
    for( int v : G[u] ) if( !vis[v] && v != fa ) fds( v , u ) , mx[u] = max( mx[u] , siz[v] ) , siz[u] += siz[v];
}
void sdf( int u , int fa ) {
    mx[u] = max( mx[u] , S - siz[u] );
    if( mx[u] < mx[pr] ) pr = u;
    for( int v : G[u] ) if( !vis[v] && v != fa ) sdf( v , u );
}
int getit( int u ) {
    pr = u;
    fds( u , u );
    S = siz[u];
    sdf( u , u );
    return pr;
}
int g[MAXN] , gg[MAXN] , ok[MAXN];
vector<int> pts , pall;
void dfs( int u , int fa ) {
    pts.pb( u );
    for( int v : G[u] ) if( !vis[v] && v != fa ) {
        g[v] = gcd( g[u] , A[v] );
        dfs( v , u );
    }
}
long long ans[MAXN];
void work( int u ) {
    vis[u] = 1;
    pall.clear();
    for( int x : divs[A[u]] ) ++ ans[x] , ++ gg[x] , pall.pb( x );
    for( int v : G[u] ) if( !vis[v] ) {
        pts.clear();
        g[v] = gcd( A[u] , A[v] ) , dfs(v, u);
        for( int x : pts )
            for( int p : divs[g[x]] )
                ans[p] += gg[p];
        for( int x : pts )
            for( int p : divs[g[x]] )
                ++ gg[p] , pall.pb( p );
    }
    for( int t : pall ) gg[t] = 0;
    for( int v : G[u] ) if( !vis[v] ) work( getit( v ) );
}
void solve() {
    prewk();
    cin >> n;
    rep( i , 1 , n ) scanf("%d",A + i);
    int u , v;
    rep( i , 2 , n ) {
        scanf("%d%d",&u,&v);
        G[u].pb( v ) , G[v].pb( u );
    }
    work( getit( 1 ) );
    for( int i = en ; i ; -- i )
        for (int j = 1; j * pri[i] < MAXN; ++j)
            ans[j] -= ans[j * pri[i]];
    for( int i = 1 ; i < MAXN ; ++ i ) if( ans[i] ) printf("%d %lld\n",i,ans[i]);
}

signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}