Acwing-Hankson的趣味题-(dfs求因子+质数，因子，数字大小的各种关系的整理)

Hankson的趣味题

题意：
就是给你多组测试样例，每次给你a0,a1,b0,b1，让你找出有多少不同的x，满足gcd(a0,x)=a1并且lcm(b0,x)=b1。T = 2000,1≤a0,a1,b0,b1≤2∗1e9。

思考：

1. 很久以前刷acwing的时候，没把这题当回事，就随便看了看就过了。这次CCPC网络赛就考了，而我却还不知道dfs求因子是什么东西，顺便整理一下所有质数因子数字大小之间的关系。
2. 先说这题，由于lcm(b0,x) = b1，那么x肯定是b1的因子，如果我暴力枚举所有的b1的因子，复杂度就是根号下b×T，这样就超时了。那gcd(a0,x) = a1,也就是x是a1的倍数，如果枚举倍数复杂度n/a1×T也很高。那怎么办呢？感觉也没有快速求因子或者倍数的算法呀？
3. 实际上，对于一个数的因子，这个因子肯定都是他的质因子组成的。 所以我可以先分解质因数，然后dfs暴力枚举每个质因子取多少次方，这样就可以找到所有的因子。由于1到n种的质数 = n/ln(n)。 所以可以先预处理出根号下(2e9)的所有质因子，然后用n/ln(n)的试除法来对b进行质因数分解。然后就是dfs了，但是我想，反正你还是要把所有的因子给求出来，但是平均每个数的因子 = log(n)个。 所以因子并不多。这样复杂度总体就是Tn/ln(n) = 1e7，对于枚举出的因子一共Tlog(n)个，然后判断gcd和lcm所以复杂度Tlog(n)log(n)，加起来就是O(Tn/ln(n)+Tlog(n)*log(n)) = O(2e7)。

代码：

#include
#define fi first
#define se second
#define pb push_back
#define db double
#define int long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

using namespace std;
const int mod = 1e9+7,inf = 1e18;
const int N = 2e5+10,M = 4e5+10;

int T,n,m,k;
PII va[N];
int vb[N];
int pri[M],st[M];
int cnt,cnt1,cnt2;

void init(int x)
{
	for(int i=2;i<=x;i++)
	{
		if(!st[i]) pri[++cnt] = i;
		for(int j=1;pri[j]*i<=x;j++)
		{
			st[pri[j]*i] = 1;
			if(i%pri[j]==0) break;
		}
	}	
}

void dfs(int now,int sum)
{
	if(now>cnt1)
	{
		vb[++cnt2] = sum;
		return ;
	}
	int res = 1;
	for(int i=0;i<=va[now].se;i++)
	{
		dfs(now+1,sum*res);
		res *= va[now].fi;
	}
}

int gcd(int a,int b)
{
	if(!b) return a;
	return gcd(b,a%b);
}

int lcm(int a,int b)
{
	return a/gcd(a,b)*b;
}

signed main()
{
	IOS;
	init(4e5+5);
	//由于分解质因数或者找因子都是根号下n的复杂度
	//所以这里晒的时候只要晒根号下n就可以了,对于大的质数就剩下一个了
	//因为如果是两个的话大于4e5的质数的平方>1e9了都.
	cin>>T;
	while(T--)
	{
		int a0,a1,b0,b1;
		cin>>a0>>a1>>b0>>b1;
		cnt1 = 0;cnt2 = 0;int tmp = b1;
		for(int i=1;pri[i]<=tmp/pri[i];i++)
		{
			int res = 0;
			while(tmp%pri[i]==0)
			{
				res++;
				tmp /= pri[i];
			}
			va[++cnt1] = {pri[i],res};
		}
		if(tmp>1) va[++cnt1] = {tmp,1};
		dfs(1,1);
		int ans = 0;
		for(int i=1;i<=cnt2;i++)
		{
			if(lcm(b0,vb[i])==b1&&gcd(a0,vb[i])==a1) ans++;
		}
		cout<<ans<<"\n";
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

总结：
以后最好搞懂那些优化复杂度的各种算法。