CF990G GCD Counting

CF 990 G GCD Counting

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

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

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

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

考虑点分治,当前点分的根是 uu ,怎么求答案。

我们假设当前已经考虑到了子树 vv ,之前已经找到过的所有子树与根和起来称作 uu 。那么我们现在需要算:

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

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

d=12×105x=1siz[u]y=1siz[v][dA[x],dB[y]]\sum_{d=1}^{2\times10^5} \sum_{x=1}^{siz[u]}\sum_{y=1}^{siz[v]} [d|A[x],d|B[y]]

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

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

#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();
}
\