AcWing 200. Hankson的趣味题

一.题目链接

二.思路

T组测试数据，每次给出a,b,c,d。gcd(a,x)=b,lcm(c,x)=d。求满足条件的x的个数。
由题意可知，x是d的约数。
所以暴力的方法就是：
枚举d的所有约数，然后判断一下条件是否成立（即gcd(a,x)==b && c*x/gcd(c,x)==d）
暴力求所有约数的方法：$O(\sqrt{N})$。其中N可以取到$2\ast 10^9$
时间复杂度：$O(T\ast \sqrt{N}))$ 会超时。
本题的时间复杂度瓶颈在求d的所有约数上面。

思路参考：https://www.acwing.com/solution/content/3101/

三.代码

#include 
#include 
#include 

using namespace std;

typedef long long LL;

const int N = 50010;

struct fact{
    int p, s;
}factor[N];//将d分解质因数
int fcnt;
int T;//t组测试数据
int dividor[1601], dcnt;//存储d的所有约数
int primes[N], cnt;
bool st[N];
//线性筛
void init(int n)
{
    for(int i = 2; i <= n; i ++)
    {
        if(!st[i]) primes[cnt ++] = i;
        for(int j = 0; i * primes[j] <= n; j ++)
        {
            st[i * primes[j]] = true;
            if(i % primes[j] == 0) break;
        }
    }
}
//暴搜d的所有约数
void dfs(int u, int p)
{   //如果考虑完所有的质数之后
    if(u == fcnt)
    {
        dividor[dcnt ++] = p;
        return;
    }
    for(int i = 0; i <= factor[u].s; i ++)
    {
        dfs(u + 1, p);
        p *= factor[u].p;
    }
}

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a; 
}
int main()
{
    init(N);
    cin >> T;
    while(T --)
    {
        int a, b, c, d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        //将d分解质因数 此时的复杂的不是O(根号N) 而是n/ln(n)
        //这里不是从2开始枚举到根号n 而是枚举1~根号N的每一个质数。所以时间复杂度取决与质数个数也就是
        //n/(ln n)
        fcnt = 0;//统计质因子的数量
        int t = d;
        for(int i = 0; primes[i] <= t / primes[i]; i ++)
        {
            int p = primes[i];
            if(t % p == 0)
            {
                int s = 0;
                while(t % p == 0) s ++, t /= p;
                factor[fcnt ++] = {p, s};
            }
        }
        //如果t大于1的话 说明是最后一个质因数。
        if(t > 1) factor[fcnt ++] = {t, 1};
        
        dcnt = 0;
        dfs(0, 1);//第几个质数,p存储答案
        int res = 0;
        for(int i = 0; i < dcnt; i ++)
        {
            int x = dividor[i];
            if(gcd(a, x) == b && (LL)c * x / gcd(c, x) == d) res ++;
        }
        cout << res << endl;
    }
    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

四.总结

本题最为核心的地方，在于时间复杂度的分析。
1

• 当我们要求一个数n的约数时：
  暴力方法：直接试除法$O(\sqrt{N})$
  优化方法：用$1到\sqrt{N}$的所有质数，去试除。时间复杂度可以降到$\frac{n}{lnn}$。
• $2\ast 10^9约数个数最多的有1536个$
• $2^{31}-1约数个数最多有1600个$
• $\sqrt{2\ast 10^9}在40000到50000之间$