我要招人

去企业版

首页 > 试题广场 >

游游的因子计算

[编程题]游游的因子计算

热度指数：743 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

游游拿到了两个正整数 $a$ 和 $b$ ，请你告诉她 $a*b$ 有哪些因子。

输入描述:

两个正整数和。

输出描述:

第一行输出一个正整数，代表的因子数量。
第二行输出个正整数，代表的所有因子，从小到大排列。

示例1

输入

6 2

输出

6
1 2 3 4 6 12

算法知识视频讲解

Handa_Rei

时间相当优的一种解法

所有用例花了16ms
factorize是一种快速分解质因数的算法，对于非大质数的分解十分快速。
比如在a和b中，2一共出现了5次，3一共出现了4次。
那么 $a*b$ 的因数可以表示 $2^i*3^j$ ,其中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 << " ";
    }
}

编辑于 2023-09-22 00:16:35 回复(0)

小师弟想要offer

#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")

发表于 2023-07-19 21:22:18 回复(2)

在干饭的喜羊羊很想退休

import java.util.Scanner;

import java.util.PriorityQueue;

import java.util.ArrayList;

import java.util.Collections;

import java.util.TreeSet;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

long a = in.nextLong();

long b = in.nextLong();

PriorityQueue<Long> a1 = new PriorityQueue<>();

PriorityQueue<Long> b1 = new PriorityQueue<>();

PriorityQueue<Long> used = new PriorityQueue<>();

boolean use = false;

for(long i = 1; i <= Math.max(((long) Math.sqrt(a)) + 1, ((long) Math.sqrt(b)) + 1); i++ ){

if(a % i == 0){

a1.offer(i);

a1.offer(a / i);

}

if(b % i == 0){

b1.offer(i);

b1.offer(b / i);

}

TreeSet<Long> q = new TreeSet<>();

long az = a1.size();

long bz = b1.size();

for(long i = 0; i < az; i++){

long t = a1.poll();

if(!use){

for(long j = 0; j < bz; j++){

long e = b1.poll();

q.add(t * e);

used.offer(e);

}

use = true;

}else{

for(long j = 0; j < bz; j++){

long e = used.poll();

q.add(t * e);

b1.offer(e);

}

use = false;

}

long sizee = q.size();

System.out.println(sizee);

for(long i = 0; i < sizee; i++){

if (i > 0) System.out.print(" ");

System.out.print(q.pollFirst());

}

System.out.println();

}

发表于 2025-09-02 19:38:50 回复(0)

gaoyin

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;
    }
}

发表于 2023-07-17 11:19:58 回复(1)