UOJ192 最强跳蚤
2020-02-05 16:00:39来源:博客园 阅读 ()
UOJ192 最强跳蚤
题目链接
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;
}
原文链接:https://www.cnblogs.com/wxyww/p/uoj192.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:二叉树(四)二叉堆
- 32.QT-制作最强电压电阻表盘,可以自定义颜色,图标,文字标签- 2018-07-03
- 20个最强的基于浏览器的在线代码编辑器 2018-06-27
- 20个最强的基于浏览器的在线代码编辑器 2018-06-18
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash