游游的因子计算

时间相当优的一种解法

所有用例花了16ms
factorize是一种快速分解质因数的算法，对于非大质数的分解十分快速。
比如在a和b中，2一共出现了5次，3一共出现了4次。
那么的因数可以表示,其中i的取值范围为0-2，j的取值范围为0-5。递归求解即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<ll> ans;
unordered_map<ll, int> cnt;
vector<vector<ll>> pair_wise;

auto& factorize(unordered_map<ll, int>& cnt, ll n) {
    while (n % 2 == 0) {
        cnt[2]++;
        n /= 2;
    }
    for (int i = 3; i <= std::sqrt(n); i += 2) {
        while (n % i == 0) {
            cnt[i]++;
            n /= i;
        }
    }
    if (n > 2)
        cnt[n]++;
    return cnt;
}

void dfs(int idx, ll acc) {
    if (idx == pair_wise.size())
        ans.push_back(acc);
    else {
        ll cur = 1;
        ll prime = pair_wise[idx][0], number = pair_wise[idx][1];
        for (int i = 0; i < number + 1; i++) {
            dfs(idx + 1, acc * cur);
            cur *= prime;
        }
    }
}



int main() {
    ll a, b;
    cin >> a >> b;
    factorize(cnt, a);
    factorize(cnt, b);
    for (auto &[key, val] : cnt) {
        pair_wise.push_back({key, val});
    }
    dfs(0, 1);
    std::sort(ans.begin(), ans.end());
    cout << ans.size() << endl;
    for (auto n : ans) {
        cout << n << " ";
    }
}

#include <iostream>
#include <linux/limits.h>
#include <set>
#include <algorithm>
#include <vector>
using namespace std;

set<long long > mp;

void solve(int a , vector<int> & v){
    for(int i =1 ; i *i <= a ; i ++){
        if(a % i == 0){
            v.push_back(i);
            v.push_back(a / i);
        }
    }
}
int main() {
    long long  a, b;
    cin >> a>> b;
    vector<int > av,bv;
    solve(a , av);
    solve(b , bv);

    for(int i : av){
        for(int j : bv){
            mp.insert(i * j);
        }
    }
    cout<<mp.size()<<endl;
    for(auto i : mp){
        cout<< i <<" ";
    }
    cout<<endl;
}
// 64 位输出请用 printf("%lld")

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        int a = Integer.parseInt(s.split(" ")[0]);
        int b = Integer.parseInt(s.split(" ")[1]);
        List<Integer> la = getFactor(a);
        List<Integer> lb = getFactor(b);
        Set<Long> set = new TreeSet<>();
        for (Integer value : la) {
            for (Integer integer : lb) {
                set.add((long) value * integer);
            }
        }
        System.out.println(set.size());
        for (Long t : set) {
            System.out.print(t);
            System.out.print(" ");
        }
        System.out.println();
    }

    public static List<Integer> getFactor(int num) {
        List<Integer> arr = new ArrayList<>();
        for (int i = 1; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                arr.add(i);
                int n = num / i;
                if (n != i) {
                    arr.add(n);
                }
            }
        }
        return arr;
    }
}