两个正整数a，b，请问a∗b有哪些因子

#1≤a,b≤1e9

求因子的数量并给出所有因子

本题无脑的暴力显然不能过，但用set存数，加上考虑到a*b的所有约数其实就是a的所有约数和b的所有约数分别相乘(核心）

补充常识：int范围内数的约数个数最多为1600，2e9数的约数个数最多为1536，这也是本题能这样暴力的基础

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
#include <bits/stdc++.h>
using namespace std;
# define int long long

const int N = 1e5 + 10;
const int M = 2e5 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;

int n, m;

set<int> yueshu(int x) {
    set<int> st;
    for (int i = 1; i * i <= x; i++) {
        if (x % i == 0){//这个大括号很重要，我debug的一个多小时的罪魁祸首
            st.insert(i);
        if (i * i != x)
            st.insert(x / i);}
    }
    return st;
}

signed main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int t;
    t = 1;
    //cin>>t;
    while (t--) {
        int a, b;
        cin >> a >> b;
        set<int> s1, s2, ans;
        s1 = yueshu(a);
        s2 = yueshu(b);
        for (auto x : s1) {
            for (auto y : s2) {
                ans.insert(x * y);
            }
        }
        cout << ans.size() << endl;
        for (auto x : ans)
            cout << x << " ";
    }
    return 0;
}

但上面这种解法显然无法解决多个数的相乘的所有约数，考虑推广问题并给出dfs解法
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=62967953（别人用lamda函数的解法，有待学习）

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
#include <bits/stdc++.h>
using namespace std;
# define int long long
typedef pair<int,int>pii;
const int N = 1e5 + 10;
const int M = 2e5 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;

int n, m;
map<int ,int>mp;

vector<int>ans;
void dfs(int u,int s,vector<pii>&res){
if(u==res.size())
{
   // cout<<u<<" "<<v.size()<<endl;
    ans.push_back(s);
    return ;
}
for(int j=0;j<=res[u].second;j++){
    dfs(u+1,s,res);
   // cout<<u<<" "<<j<<" "<<s<<endl;
    s*=res[u].first;
}
}

signed main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int t;
    t = 1;

    while (t--) {
        int a, b;
        cin >> a >> b;
       for(int i=2;i*i<=a;i++){
        if(a%i==0){
           while(a%i==0){
            mp[i]++;
            a/=i;
           }
        }
       }
       if(a>1)mp[a]++;
        for(int i=2;i*i<=b;i++){
        if(b%i==0){
           while(b%i==0){
            mp[i]++;
            b/=i;
           }
        }
       }
       if(b>1)mp[b]++;
  /*for (auto it = mp.begin(); it != mp.end(); ++it) {
    v.push_back(*it);
}*/
 vector<pii>v(mp.begin(),mp.end());
       dfs(0,1,v);
       //for(auto[x,y]:v)cout<<x<<" "<<y<<endl;
       cout<<ans.size()<<endl;
       sort(ans.begin(),ans.end());
       for(auto x:ans){
        cout<<x<<" ";
       }
    }
    return 0;
}