problem

给出一个n个点带边权的树，问有多少对\((u,v)\)满足\(u\)到\(v\)路径上边权的乘积为完全平方数。

\(n\le 10^5,w\le 10^8\)

solution

一个比较朴素的处理方法就是：设第i个质因子权值为\(2^{i-1}\)，将每个边权质因子分解，并将所有质因子的权值异或起来，然后得到一个新的权值。这样问题就转化为了求有多少对\((u,v)\)满足从\(u\)到\(v\)路径上的权值异或和为0。直接书上前缀和一下就行。

但是当\(w=10^8\)时显然不行，考虑给每个质因子随机赋一个\([0,2^{64}]\)中的值，然后用同样的方法异或起来。这样满足条件的路径一定可以被找到。不满足条件的路径只有\(\frac{1}{2^{64}}\)误算。

然后考虑如何计算每个数字的质因子，先线性筛出\([1,\sqrt{w}]\)中的质因子，并对其重新赋权值。对于大于\(\sqrt{w}\)的质因子单独处理一下。

code

/*

* @Author: wxyww

* @Date: 2020-02-05 16:57:50

* @Last Modified time: 2020-02-05 18:21:14

*/

#include<map>

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cmath>

#include<ctime>

#include<bitset>

#include<cstring>

#include<algorithm>

#include<string>

#include<queue>

#include<vector>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int N = 100010;

ll read() {

	ll x=0,f=1;char c=getchar();

	while(c<'0'||c>'9') {

		if(c=='-') f=-1;

		c=getchar();

	}

	while(c>='0'&&c<='9') {

		x=x*10+c-'0';

		c=getchar();

	}

	return x*f;

}

struct node {

	int v,nxt;ull w;

}e[N << 1];

int head[N],ejs;

void add(int u,int v,ull w) {

	e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs;e[ejs].w = w;

}

map<int,ull>ma;

ull Rand() {

	return (ull)rand() * (ull)rand() * (ull)rand() * (ull)rand() * (ull)rand();

}

ull val[N];

int vis[N],pri[N],tot;

void pre() {

	for(int i = 2;i <= 10000;++i) {

		if(!vis[i]) {

			pri[++tot] = i;

			val[tot] = Rand();

		}

		for(int j = 1;j <= tot && i * pri[j] <= 10000;++j) {

			vis[pri[j] * i] = 1;

			if(i % pri[j] == 0) break;

		}

	}

}

ull get(int x) {

	ull ret = 0;

	for(int i = 1;i <= tot;++i) {

		while(x % pri[i] == 0) {

			x /= pri[i];

			ret ^= val[i];

		}

	}

	if(x != 1) {

		if(!ma.count(x)) ma[x] = Rand();

		ret ^= ma[x];

	}

	return ret;

}

ull dis[N];

ll anss;

map<ull,int>ans;

void dfs(int u,int fa) {

	anss += ans[dis[u]] * 2;

	ans[dis[u]]++;

	for(int i = head[u];i;i = e[i].nxt) {

		int v = e[i].v;if(v == fa) continue;

		dis[v] = dis[u] ^ e[i].w;

		dfs(v,u);

	}

}

int main() {

	pre();

	int n = read();

	for(int i = 1;i < n;++i) {

		int u = read(),v = read();ull w = get(read());

		add(u,v,w);add(v,u,w);

	}

	dfs(1,0);

	cout<<anss;

	return 0;

}

巴特西

UOJ192 最强跳蚤

problem

solution

code

最新文章

热门文章