「uoj 192」「UR 14」最强跳蚤 (异或性质,Hash,数论,拆路径)

uoj 192
题意:给出一个带边权树,求出树上所有路径积为完全平方数的条数。

我们考虑完全平方数的条件,则它的每个质因数出现偶数次
那么我们联想到异或,我们可以记录路径异或值,然后问题转化为多少条路径异或和为0
这里我们可以对每个质因数指定一个Hash值,然后异或起来就行
注意根据生日攻击的原理,权值范围要远大于$n^2$,那么我们$\text{rand}$一个long long 范围的数
具体有一个近似的公式
$$
\sqrt{\frac \pi 2 n}
$$
那么我们预处理$\sqrt{w}$以内的质数,每次枚举质数分解质因数即可,注意数本身是个大质数的情况
然后就可以求多少条路径异或和为0了,这是经典问题,即拆分路径以后做

1、异或–两两消除
2、Hash–暴力不行时想想

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<string>
#include<ctime>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    int n, en, hd[100000 + 5], vis[10000 + 5], pri[10000 + 5], tot, cnt;
    LL dis[100000 + 5];
    map<int, LL > hsh;
    struct edge {int v; LL w; int nxt;} ed[200000 + 5];

    void ins(int x, int y, LL w) {ed[++en] = (edge){y, w, hd[x]}, hd[x] = en;}
    void dfs(int u, int fa, LL D) {
        dis[++cnt] = D;
        for (int i = hd[u]; i >= 0; i = ed[i].nxt) {
            edge &e = ed[i];
            if (e.v != fa) dfs(e.v, u, D ^ e.w);
        }
    }

    void clean() {
        en = -1, ms(hd, -1);
    }
    int solve() {

        srand((int)time(0));

        clean();

        for (int i = 2; i <= 10000; ++i) {
            if (!vis[i]) pri[++tot] = i; 
            for (int j = 1; j <= tot && pri[j] * i <= 10000; ++j) {
                vis[pri[j] * i] = 1;
                if (i % pri[j] == 0) break ;
            }
        }

        scanf("%d", &n);
        for (int x, y, w, i = 1; i < n; ++i) {
            scanf("%d%d%d", &x, &y, &w);
            LL hh = 0;
            for (int j = 1; j <= tot; ++j) {
                if (w % pri[j] == 0) {
                    if (hsh.find(pri[j]) == hsh.end()) hsh[pri[j]] = (LL)rand() << 31ll | (LL)rand(); 
                    while (w % pri[j] == 0) w /= pri[j], hh ^= hsh[pri[j]];
                }
            }
            if (w != 1) {
                if (hsh.find(w) == hsh.end()) hsh[w] = (LL)rand() << 31ll | (LL)rand(); 
                hh ^= hsh[w];
            }
            ins(x, y, hh), ins(y, x, hh);
        }
        dfs(1, 0, 0);
        sort(dis + 1, dis + 1 + cnt);
        LL ans = 0;
        int j;
        for (int i = 1; i <= cnt; i = j) {
            j = i + 1;
            while (j <= cnt && dis[j] == dis[i]) ++j;
            ans += 1ll * (j - i) * (j - i - 1ll);
        }
        cout << ans;

        return 0;
    }  
}
int main() {
    flyinthesky::solve();
    return 0;
}
------ 本文结束 ------