UOJ最强跳蚤

Posted on |

problem

给一颗树，边有边权。求经过的边权积为完全平方数的路径条数。

$n<1e5,a_i<1e8$

solution

emm

可以看出要用点分治。

可是桶不好开。

所以要考虑转换。

我们可以将任意一个数X这样表示。

$X = p_1^{a_1}* p_2^{a_2} * p_3^{a_3}$ ……

$p$ 为质数。

然后我们给所有$p_i$ 赋一个随机值$h(p_i)$。

定义 $F(X)$ 为所有 $a_i为奇数的h(p_i)的异或和$

所以，我们可以得到。

当且仅当 $F(x) = 0$ 时，$x$ 为完全平方数。

所以我们可以把 $A,B$ 两数的积用 $F(A)\oplus F(B)$ 表示，因为我们仅需要知道一个数是否为完全平方数。

然后这题就完了。

好吧，还有一些细节。

比如 $h(p_i)$ 的随机值要是 $long~long$ 范围的。这样才能保证正确性。

还有，因为 $a_i<1e8$ 不能用线性筛，所以我们要筛出 $1e4$ 以内的质数，然后对所有数用 $\frac {\sqrt a_i}{\ln n}$ 的复杂度算出 $F(a_i)$ 。

还有一点很重要，桶不能用 $map$ ，只能用 $hash$ 。

先上一份自己打的，但是被 $hack$ 数据卡T了的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#pragma GCC optimize(3)
#pragma G++ optimize(3)
#include <bits/stdc++.h>

using namespace std;

#define fst first
#define snd second
#define SZ(u) ((int) (u).size())
#define ALL(u) (u).begin(), (u).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template<typename T> inline T read()
{
	register T sum(0), fg(1);
	register char ch(getchar());
	for(; !isdigit(ch); ch = getchar()) if(ch == '-') fg = -1;
	for(;  isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) - 48 + ch;
	return sum * fg;
}

typedef long long LL;
typedef pair<int, LL> pii;
const int Maxn = 1e5 + 10, Maxv = 1e4 + 10, mod = 2333333;
vector <pii> Map[Maxn];
unordered_map <LL, LL> mp,book;
int pre[Maxn], top, Top, siz[Maxn], n;
bool vis[Maxn],bk[Maxn + 10];
long long p[Maxn] ,del[Maxn], pre_rand[Maxn + 10], stk[Maxn], ans;
LL Rand(){
	int res = rand(),res2 = rand();
	LL tmp = 1ll * res * res2;
	while(tmp <= 0) {
		if(res > res2) swap(res,res2);
		res = rand();
		tmp = 1ll * res * res2;
	}
	return tmp;
}
vector<pii> h[mod + 10];
int ask(LL number){
	int now = number % mod;
	for (int i = h[now].size() - 1;i >= 0; --i){
		if(h[now][i].snd == number)
			return h[now][i].fst;
	}
	return 0;
}
void add(LL number, int d){
	int now = number % mod;
	bool fl = 1;
	for (int i = h[now].size() - 1;i >= 0; --i){
		if(h[now][i].snd == number)
			h[now][i].fst += d,fl = 0;
	}
	if(fl)h[now].push_back((pii){d,number});
}
void init(){
	srand(19260817);
	for (int i = 2;i <= Maxv; ++i){
		if(!bk[i]){
			pre[++Top] = i;
			pre_rand[Top] = Rand();
			for (int j = i << 1; j <= Maxv; j += i) bk[j] = 1;
		}
	}
}
void div_siz(int now, int pa){
	siz[now] = 1;
	for (int i = Map[now].size() - 1; i >= 0; --i){
		int nxt = Map[now][i].fst;
		if(vis[nxt] || nxt == pa)continue;
		div_siz(nxt, now);
		siz[now] += siz[nxt];
	}
}
int div_rt(int now,int pa, int tot_siz){
	bool fg = 1;
	for (int i = Map[now].size() - 1; i >= 0; --i){
		int nxt = Map[now][i].fst;
		if(vis[nxt] || nxt == pa)continue;
		int p = div_rt(nxt,now,tot_siz);
		if(p) return p;
		if((siz[nxt] << 1) > tot_siz) fg = 0;
	}
	if((tot_siz - siz[now] << 1) > tot_siz) fg = 0;
	if(fg) return now;
	return 0;
}
LL get_p(int number){
	LL res = 0;
	for (int i = 1; i <= Top && pre[i] <= number; ++i){
		while(number % pre[i] == 0){
			res ^= pre_rand[i];
			number /= pre[i];
		}
	}
	if (number > 1){
		if (!mp[number]){ 
			mp[number] = Rand();
		}
		res ^= mp[number];
	}
	return res;
}
void get_dis(int now, int pa){
	stk[++top] = p[now];
	for (int i = Map[now].size() - 1; i >= 0; --i){
		int nxt = Map[now][i].fst;
		if(vis[nxt] || nxt == pa)continue;
		p[nxt] = p[now] ^ Map[now][i].snd;
		get_dis(nxt, now);
	}
}
void calc(int now){
	int tot = 0;
	for (int i = Map[now].size() - 1; i >= 0; --i){
		int nxt = Map[now][i].fst;
		if(vis[nxt]) continue;
		top = 0;
		p[nxt] = Map[now][i].snd;
		get_dis(nxt, now);
		for (int j = 1; j <= top; ++j){
			ans += ask(stk[j]);
		}
		for (int j = 1; j <= top; ++j)
			add(stk[j], 1), del[++tot] = stk[j];
	}
	for (int i = 1; i <= tot; ++i)
		add(del[i], -1);
}
void div_solve(int now){
	div_siz(now, 0), now = div_rt(now, 0, siz[now]), calc(now);
	vis[now] = 1;
	for (int i = Map[now].size() - 1; i >= 0; --i){
		int nxt = Map[now][i].fst;
		if(!vis[nxt]) div_solve(nxt);
	}
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("a.in", "r", stdin);
	freopen("a.out", "w", stdout);
#endif
	n = read<int>();
	init();
	for (int i = 1; i < n; ++i){
		int x = read<int>(), y = read<int>(), w = read<int>();
		LL w0 = get_p(w);
		Map[x].push_back((pii){y, w0});
		Map[y].push_back((pii){x, w0});
	}
	add(0,1);
	div_solve(1);
	printf("%lld\n",2ll * ans);
	return 0;
}

这份代码，卡了半年常，就是卡不过。

后来把手写哈希换成hash_table就过了。

感谢fatesky大佬的帮助！！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <bits/stdc++.h>

using namespace std;

#define fst first
#define snd second
#define SZ(u) ((int) (u).size())
#define ALL(u) (u).begin(), (u).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template<typename T> inline T read()
{
	register T sum(0), fg(1);
	register char ch(getchar());
	for(; !isdigit(ch); ch = getchar()) if(ch == '-') fg = -1;
	for(;  isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) - 48 + ch;
	return sum * fg;
}

typedef long long LL;
typedef pair<int, LL> pii;
const int Maxn = 1e5 + 10, Maxv = 1e4 + 10, mod = 2333333;
vector <pii> Map[Maxn];
map <LL, LL> mp,book;
int pre[Maxn], top, Top, siz[Maxn], n;
bool vis[Maxn],bk[Maxn + 10];
long long p[Maxn],del[Maxn], pre_rand[Maxn + 10], stk[Maxn], ans;
LL Rand(){
	int res = rand(),res2 = rand();
	LL tmp = 1ll * res * res2;
	while(tmp <= 0) {
		if(res > res2) swap(res,res2);
		res = rand();
		tmp = 1ll * res * res2;
	}
	return tmp;
}

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

namespace DIV
{
	cc_hash_table<LL, int> H;

	void init(){
		srand(19260817);
		for (int i = 2;i <= Maxv; ++i){
			if(!bk[i]){
				pre[++Top] = i;
				pre_rand[Top] = Rand();
				for (int j = i << 1; j <= Maxv; j += i) bk[j] = 1;
			}
		}
	}
	void div_siz(int now, int pa){
		siz[now] = 1;
		for (int i = Map[now].size() - 1; i >= 0; --i){
			int nxt = Map[now][i].fst;
			if(vis[nxt] || nxt == pa)continue;
			div_siz(nxt, now);
			siz[now] += siz[nxt];
		}
	}
	int div_rt(int now,int pa, int tot_siz){
#define p zjmsb
		bool fg = 1;
		for (int i = Map[now].size() - 1; i >= 0; --i){
			int nxt = Map[now][i].fst;
			if(vis[nxt] || nxt == pa)continue;
			int p = div_rt(nxt,now,tot_siz);
			if(p) return p;
			if((siz[nxt] << 1) > tot_siz) fg = 0;
		}
		if((tot_siz - siz[now]) * 2 > tot_siz) fg = 0;
		if(fg) return now;
		return 0;
#undef p
	}
	LL get_p(int number){
		LL res = 0;
		for (int i = 1; i <= Top && pre[i] <= number; ++i){
			while(number % pre[i] == 0){
				res ^= pre_rand[i];
				number /= pre[i];
			}
		}
		if (number > 1){
			if (!mp[number]) mp[number] = Rand();
			res ^= mp[number];
		}
		return res;
	}
	void get_dis(int now, int pa){
		stk[++top] = p[now];
		for (int i = Map[now].size() - 1; i >= 0; --i){
			int nxt = Map[now][i].fst;
			if(vis[nxt] || nxt == pa)continue;
			p[nxt] = p[now] ^ Map[now][i].snd;
			get_dis(nxt, now);
		}
	}
	void calc(int now){
		H.clear();
		++H[0];
		int tot = 0;
		for (int i = Map[now].size() - 1; i >= 0; --i){
			int nxt = Map[now][i].fst;
			if(vis[nxt]) continue;
			top = 0;
			p[nxt] = Map[now][i].snd;
			get_dis(nxt, now);
			for (int j = 1; j <= top; ++j) if(H.find(stk[j]) != H.end()) ans += H[stk[j]];
			for (int j = 1; j <= top; ++j) ++H[stk[j]];
		}
	}
	void div_solve(int now){
		div_siz(now, 0), now = div_rt(now, 0, siz[now]), calc(now);
		vis[now] = 1;
		for (int i = Map[now].size() - 1; i >= 0; --i){
			int nxt = Map[now][i].fst;
			if(!vis[nxt]) div_solve(nxt);
		}
	}
}
using namespace DIV;

int main()
{
#ifndef ONLINE_JUDGE
	freopen("zjm.in", "r", stdin);
	freopen("zjm.out", "w", stdout);
#endif
	n = read<int>();
	init();
	for (int i = 1; i < n; ++i){
		int x = read<int>(), y = read<int>(), w = read<int>();
		LL w0 = get_p(w);
		Map[x].emplace_back(y, w0);
		Map[y].emplace_back(x, w0);
	}
	div_solve(1);
	printf("%lld\n",2ll * ans);
	return 0;
}