题目描述
现在给了a0,a1,b0,b1四个数，问有多少个x满足 gcd(a0,x)=a1,lcm(x,b0)=b1;
样例
输入：
1
2
3
| 2
41 1 96 288
95 1 37 1776
|
输出:6 2
算法
由于b1是lcm(x,b0) 那必然x就是b1的约数，所以只要枚举出所有的b1的约束，满足条件的就是x
那如何求b1的约数呢，如果是单纯的暴力那肯定是超时的。
但是我们可以记录所有b1的质因子并且每个质因子的个数，来达到因式分解的目的；
（线性筛的板子写假了 primes写成了bool类型 每个质数都是1抽了一晚的烟都没看出来哪里超时了）
for(int i=1;primes[i]*primes[i]<=h&&i<=cnt;i++)
{
int s=0;
while(h%primes[i]==0) s++,h/=primes[i];
if(s!=0)in[++cntd]={primes[i],s};
}
然后再根据质因子以及每个质因子的个数深搜枚举即可
dfs(1,1);//深搜入口，第1个质因子，当前的值为1
深搜的过程
1
2
3
4
5
6
7
| void dfs(int u,int k){
if(u>cntd) {ans[++cntf]=k;return ;}//如果记录的所有质因子都遍历完那就结束
for(int i=0;i<=in[u].second;i++){
dfs(u+1,k);
k*=in[u].first;//枚举每个因子的数量
}
}
|
C++ 代码
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
| #include <bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
int cnt=0;
bool st[100010];
int primes[100010];
PII in[100010];
int num[100010];
void init(int k){
for(int i=2;i<=k;i++){
if(!st[i])primes[++cnt]=i;
for(int j=1;i*primes[j]<=k&&j<=cnt;j++){
st[i*primes[j]]=1;
if(i%primes[j]==0) break;
}
}
}
int ans[1000100];
int cntd=0,cntf=0;
void dfs(int u,int k){
if(u>cntd) {ans[++cntf]=k;return ;}
for(int i=0;i<=in[u].second;i++){
dfs(u+1,k);
k*=in[u].first;
}
}
void solve(){
int a0,a1,b0,b1;
cin>>a0>>a1>>b0>>b1;
cntd=0,cntf=0;
int h=b1;
for(int i=1;primes[i]*primes[i]<=b1&&i<=cnt;i++)
{
int s=0;
while(h%primes[i]==0) s++,h/=primes[i];
if(s!=0)in[++cntd]={primes[i],s};
}
if(h>1)in[++cntd]={h,1};
dfs(1,1);
int res=0;
//cout<<cntf<<"+++";
for(int i=1;i<=cntf;i++){
if(__gcd(ans[i],a0)==a1&&(long long)ans[i]*b0/__gcd(ans[i],b0)==b1)
res++;
}
cout<<res<<endl;
}
signed main(){
init(100000);
int _;
cin>>_;
while(_--){
solve();
}
}
|
所以呢就不快乐。