//素数筛与合数分解 //预处理O(sqrt(n)),询问O(sqrt(n)) //调用find_ini() getfac() const int maxn=3e6+5; int prime[maxn],prime_,not_prime[maxn]={1,1}; void prime_ini(){// 素数不可能筛到longlong范围 for(int i=2; i<maxn; i++){ if(!not_prime[i])prime[prime_++]=i;//把质数收录 for(int j=0; 1ll*i*prime[j]<maxn; j++){ not_prime[i*prime[j]]=1;//对每一个数字枚举他的最小因子 if(i%prime[j]==0)break;//在往后的话就不是最小因子了 } } } int fac[100][2],fac_; void getfac(int x){ // assert(x>=2) fac_=0;//清空fac for(int i=0; prime[i]<=x/prime[i]; i++){ if(x%prime[i]==0){ fac[fac_][0]=prime[i]; fac[fac_][1]=0; while(x%prime[i]==0){ fac[fac_][1]++; x/=prime[i]; } fac_++; } } if(x!=1){ fac[fac_][0]=x; fac[fac_][1]=1; fac_++; } } ////////////////////////////////////////////////////////////////////////////////////
//这个板子只能处理正数 //预处理O(n)合数分解O(lgn) //最大使用范围[1,MAXN),实际使用[1,MAXN); //调用find_ini() getfac() typedef long long ll; const ll MAXN=1e6+5; ll prime[MAXN],prime_; ll min_fac[MAXN]={-9527,1};//0,1 bool not_prime[MAXN]={true,true};//0,1 void prime_ini(){ for(ll i=2; i<MAXN; i++){ if(!not_prime[i]){ prime[prime_++]=i;//把质数收录 min_fac[i]=i; } for(ll j=0; j<prime_ && i*prime[j]<MAXN; j++){ not_prime[i*prime[j]]=true;//对每一个数字枚举他的最小因子 min_fac[i*prime[j]]=prime[j]; if(i%prime[j]==0)break;//在往后的话就不是最小因子了 } } } //当x=0,1会异常,无意义的东西 ll fac[100][2],fac_; void getfac(int x){ fac_=0; while(x!=1){ ll little=min_fac[x]; fac[fac_][0]=little; fac[fac_][1]=0; while(little!=1 && min_fac[x]==little){ x/=little; fac[fac_][1]++; } fac_++; } } //solved poj-1365