调用 fac(n) map 中会存下 \(n\) 的所有质因子（去重）
#include<bits/stdc++.h>
#define int long long
using namespace std;
using ull=unsigned long long;
mt19937 rnd(time(0));
unordered_map<int,int> mp;
int qpow(int x,int p,int mod) {int ans=1;while(p) {if(p&1) ans=(__int128)ans*x%mod;x=(__int128)x*x%mod;p>>=1;}return ans;
}
bool MR(int p) {if(p<2) return false;if(p==2) return true;if(p==3) return true;int d=p-1,r=0;while(d%2==0) r++,d>>=1;for(int k=0; k<10; k++) {int a=rnd()%(p-2)+2,x=qpow(a,d,p);if(x==1||x==p-1) continue;for(int i=0; i<r-1; i++) {x=(__int128)x*x%p;if(x==p-1) break;}if(x!=p-1) return false;}return true;
}
int PR(int x) {int s=0,t=0,c=rnd()%(x-1)+1,val=1;for(int i=1; ; i*=2,s=t) {for(int j=1; j<=i; j++) {t=((__int128)t*t%x+c)%x;val=(__int128)val*abs(t-s)%x;if(j%127==0||j==i) {int d=__gcd(val,x);if(d>1) return d;}}}
}
void fac(int x) {if(x==1) return;if(MR(x)) return mp[x],void();int p=PR(x);while(p==x) p=PR(x);while(x%p==0) x/=p;fac(x),fac(p);
}