一个绝妙的整除判定优化

#include<bits/stdc++.h>
using namespace std;
const int maxn=1<<16;

using u32=uint32_t;using u64=uint64_t;
bool np[maxn];
u32 p[maxn];int pc;
u64 isd_p[maxn];

void eul(){
	for(int i=2;i<maxn;++i){
		if(!np[i])p[++pc]=i,isd_p[pc]=-1ull/i+1;
		for(int j=1;j<=pc&&p[j]*i<maxn;++j){
			np[p[j]*i]=1;if((u32)i*isd_p[j]<isd_p[j])break;
		}
	}
}

vector<u32> pfac(u64 x){
	vector<u32>res;
	for(int i=1;i<=pc&&(u64)p[i]*p[i]<=x;i+=8){
		#define do_with(i)\
		if(isd_p[i]*x<isd_p[i]){\
			res.push_back(p[i]);\
			do x/=p[i];while(x%p[i]==0);\
		}
		do_with(i)do_with(i+1)do_with(i+2)do_with(i+3);
		do_with(i+4)do_with(i+5)do_with(i+6)do_with(i+7);
	}
	if(x!=1)res.push_back(x);
	return res;
}
vector<u32> pfac_ntv(u32 x){
	vector<u32>res;
	for(int i=1;i<=pc&&(u64)p[i]*p[i]<=x;++i){
		if(x%p[i]==0){
			res.push_back(p[i]);while(x%p[i]==0)x/=p[i];
		}
	}
	if(x!=1)res.push_back(x);
	return res;
}
signed main() {
	ios::sync_with_stdio(0),cin.tie(0);
	eul();
	u32 hava=0;
	mt19937 rng(0);
	for(int i=0;i<(int)1e6;++i){
		u32 x=p[(u64)i*i%pc+1]*p[(u64)i*(u64)i*(u64)i%pc+1];
		// u32 x=rng();
		auto z=pfac(x);hava^=z.size();
		// assert(z==pfac_ntv(x));
	}
	cerr<<hava<<clock()*1./CLOCKS_PER_SEC;
	cerr<<endl;
}
/*
g++ te.cpp -o te -g -std=c++14 -Wall -Wshadow -fsanitize=undefined,address && ./te < in.in

*/