Hankson的趣味题

# 题意

t组数据，每组数据包含：

给定a,b,c,d,求x的个数，x满足gcd(a,x)=b , lcm(c,x)=d

t ∈ [1,2000]

a,b,c,d ∈ [1 , 2e9]

# 题解

d的约数上界是√d , 但是1～d中平均每个数的约数个数大约只有log d，即约数个数通常远远达不到上界，

2³¹-1内的数字约数个数不超过1600。

因为lcm(c,x)=d，所以x一定是d的约数，枚举所有d的约数，判断满不满足以上两个条件，

这样的复杂度是O(t * √d *log d)

约数是由质因子构成的用质因子的组合求所有约数时间复杂度

就是O(√d)预处理所有质数，然后O(t*1600*log d)

总的复杂度为O(√d+t*1600*log d)

因为组合最多有1600暴力搜索即可，

两个状态当前枚举的质因子，枚举到的约数

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 #define pii pair<int,int>
 4 #define prime first
 5 #define count second
 6 using namespace std;
 7 const int N=5e5+10;
 8 int primes[N],cnt;
 9 bool st[N];
10 int dcnt,fcnt;
11 pii factor[1600];
12 int divide[N];
13 void get_primes(int n){
14     for(int i=2;i<=n;i++){
15         if(!st[i]) primes[cnt++]=i;
16         for(int j=0;primes[j]<=n/i;j++){
17             st[primes[j]*i]=1;
18             if(i%primes[j]==0) break;
19         }
20     }
21 }
22 int gcd(int a,int b){return b?gcd(b,a%b):a;}
23 void dfs(int u,int p){
24     if(u == fcnt){//从0开始，越界了
25         divide[dcnt++]=p;
26         return;
27     }
28     for(int i=0;i<=factor[u].count;i++){
29         dfs(u+1,p);
30         p *= factor[u].prime;
31     }
32 }
33 int main(){
34     get_primes(N-1);
35     int t;
36     cin>>t;
37     while(t--){
38         int a,b,c,d;
39         cin>>a>>b>>c>>d;
40         fcnt=0;
41         int t=d;
42         for(int i=0;primes[i]<=t/primes[i];i++){
43             int p=primes[i];
44             if(t%p==0) {
45                 int sum = 0;
46                 while (t % p == 0) {
47                     sum++;
48                     t /= p;
49                 }
50                 factor[fcnt++] = {p, sum};
51             }
52         }
53         if(t > 1) factor[fcnt++]={t,1};
54 
55         dcnt=0;
56         dfs(0,1);
57         int ans=0;
58         for(int i=0;i<dcnt;i++){
59             int x=divide[i];
60             if(gcd(a,x)==b && (ll)c*x/gcd(c,x)==d)
61                 ans++;
62         }
63         cout<<ans<<endl;
64     }
65     return 0;
66 }