题解：P12001 在小小的奶龙山里面挖呀挖呀挖

比题解更无脑的做法。

请注意算法常数对时间效率的影响。

加上

5s

时限，说明如果常数够小可以通过。

发现

10^5

以内的素数只有

10^4

个，发现不能开

n\times 10^4

的数组，那么将询问离线下来，对于每个素数考虑，树上差分维护。假设当前处理素数

p

，记

ct_x

表示

1\sim x

路径上的点有多少个

a_i

满足

p

整除

a_i

。这个显然可以 dfs

O(n)

更新。

但是 dfs 更新太慢了，考虑卡常经典操作，将树拍成 dfs 序更新即可，求 LCA 用的 ST 表，最大点不超过一坤秒。

CPP

#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t;i += p)
#define drep(i,s,t,p) for(int i = s;i >= t;i -= p)
#ifdef LOCAL
  auto I = freopen("in.in","r",stdin),O = freopen("out.out","w",stdout);
#else
  auto I = stdin,O = stdout;
#endif
using ll = long long;using ull = unsigned long long;
using db = double;using ldb = long double;
const int N = 5e4 + 10;
#define eb emplace_back
vector<int> e[N],prime;
bitset<100010> vis;
int ct[N],n,m,a[N],u[N],v[N],dfn[N],tim,st[18][N],ans[N],lca[N],F[N],rdfn[N];
void shai(int n){
	for(int i = 2;i <= 100000; ++i){
		if(!vis[i]) prime.emplace_back(i);
		for(auto j:prime){
			if(i * j > n) break;
			vis[i * j] = true;
			if(i % j == 0) break;
		}
	}
}
void dfs(int x,int fa){
	st[0][dfn[x] = ++tim] = fa;F[x] = fa;
	rdfn[tim] = x;
	for(auto y:e[x]) if(y ^ fa) dfs(y,x);
}
int get(int x,int y){return dfn[x] < dfn[y]?x:y;}
int LCA(int x,int y){
	if(x == y) return x;
	if((x = dfn[x]) > (y = dfn[y])) swap(x,y);
	int k = __lg(y-x++);
	return get(st[k][x],st[k][y-(1<<k)+1]);
}
void pdfs(const int &now){
	for(int i = 1;i <= n; ++i){
		int x = rdfn[i];
		ct[x] = ct[F[x]];
		ct[x] += a[x]%now == 0;
	}
}
signed main(){
  cin.tie(nullptr)->sync_with_stdio(false);
	shai(100000);
	cin>>n>>m;
	for(int i = 1;i <= n; ++i) cin>>a[i];
	for(int i = 1,u,v;i < n; ++i) cin>>u>>v,e[u].eb(v),e[v].eb(u);
	dfs(1,0);
	for(int j = 1;j <= __lg(n); ++j)
		for(int i = 1;i + (1 << j) - 1 <= n; ++i)
			st[j][i] = get(st[j-1][i],st[j-1][i+(1<<(j-1))]);
	for(int i = 1;i <= m; ++i){
		cin>>u[i]>>v[i],lca[i] = LCA(u[i],v[i]);
	}
	for(auto now:prime){
		pdfs(now);
		for(int i = 1;i <= m; ++i){
			if(ct[u[i]] + ct[v[i]] - ct[lca[i]] - ct[F[lca[i]]]){
				ans[i]++;
			}
		}
	}
	for(int i = 1;i <= m; ++i) cout<<ans[i]<<'\n';
}

题解：P12001 在小小的奶龙山里面挖呀挖呀挖

文章操作

相关推荐

评论

题解：P12001 在小小的奶龙山里面挖呀挖呀挖