luogu 1072 Hankson 的趣味题 唯一分解定理+线性筛

貌似是比大多数题解优的 $O(n^2logn)$ ~

Code: 

#include <bits/stdc++.h>  
#define N 50004
#define setIO(s) freopen(s".in","r",stdin)      , freopen(s".out","w",stdout) 
using namespace std;   
struct Node 
{
	int prime,p; 
	Node(int prime=0,int p=0):prime(prime),p(p){}  
}; 
vector<Node>v;   
int tot,re=0,a0,a1,b0,b1,h,cons;       
int prime[N],vis[N]; 
void init() 
{ 
	int i,j; 
	for(i=2;i<N;++i) 
	{
		if(!vis[i]) prime[++tot]=i; 
		for(j=1;j<=tot&&i*prime[j]<N;++j) 
		{
			vis[i*prime[j]]=1; 
			if(i%prime[j]==0) break;    
		}
	}
}   
void dfs(int pos,int num) 
{   
	int i,j; 
	for(i=1;i<=v[pos].p;++i) 
	{
		num*=v[pos].prime;          
		if(__gcd(num*cons, a0)==a1) 
		{
			++re;        
	    }
	    for(j=pos+1;j<v.size();++j) dfs(j,num);   
	}
}
void solve() 
{
	int i,j;   
	scanf("%d%d%d%d",&a0,&a1,&b0,&b1),cons=b1,h=b0,re=0;     
	for(i=1;i<=tot&&h>=prime[i];++i)       
	{
		if(h%prime[i]==0) 
		{   
			int cc=0,pp=cons; 
			for(;h%prime[i]==0;h/=prime[i]) ++cc,pp/=prime[i];   
			if(pp%prime[i])     // 可自由分配 
			{
				v.push_back(Node(prime[i],cc)); 
				for(;cons%prime[i]==0;cons/=prime[i]);       
			}   
		}   
	} 
	if(h!=1) 
	{
		if((cons/h)%h)
		    v.push_back(Node(h,1)),cons/=h;   
	} 
	for(i=0;i<v.size();++i) 
		dfs(i,1);    
	v.clear();   
    printf("%d
",re+(__gcd(cons,a0)==a1)); 
}
int main() 
{
	int T,i; 
	init();  
	// setIO("input");  
	scanf("%d",&T); 
	for(i=1;i<=T;++i) solve(); 
	return 0; 
}