最小公倍数

╰+哭是因爲堅強的太久メ 2022-11-14 10:24 143阅读 0赞

#include <iostream>
    #include <cstdio>
    #include <vector>
    #include <map>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    
    map<int, int> prime_cnt, tmp_cnt; // 用于存放质因子以及其对应的最大次数
    
    void computePrimeFactorCount(int num)
    {
        
    	// printf("%d进入computePrimeFactorCount函数！\n", num);
    	for (int i = 2; num != 1;)
    	{
        
    		if (num % i == 0)
    		{
        
    			tmp_cnt[i]++;
    			num /= i;
    		}
    		else
    		{
        
    			i++;
    		}
    	}
    
    	// 更新参数
    	map<int, int>::iterator iter = tmp_cnt.begin();
    	while (iter != tmp_cnt.end())
    	{
        
    		prime_cnt[iter->first] = max(prime_cnt[iter->first], iter->second);
    		iter++;
    	}
    	tmp_cnt.clear();  // 每次统计完成后都将辅助统计次数的map清空，方便进行下一轮的统计
    }
    
    int main(int argc, char const *argv[])
    {
        
    	std::ios::sync_with_stdio(false);
    
    	// 输入数据
    	int n;
    	cin >> n;
    	for (int i = 0; i < n; i++)
    	{
        
    		int num;
    		cin >> num;
    		computePrimeFactorCount(num);
    	}
    	map<int, int>::iterator iter = prime_cnt.begin();
    	int ans = 1;  // 注意初始值为1，不是0
    	while (iter != prime_cnt.end())
    	{
        
    		// printf("%d-->%d\n", iter->first, iter->second);
    		ans *= pow(iter->first, iter->second);
    		iter++;
    	}
    	cout << ans << endl;
    
    	return 0;
    }
    
    /*
    实例：
    4
    2 3 5 6  30
    
    5
    2 3 5 6 8  120
    
    5
    3 5 15 7 2  210
    
    7
    2 3 4 5 6 7 15  420
    */

发表评论取消回复

表情：

评论列表（有 0 条评论，143人围观）

还没有评论，来说两句吧...

相关阅读

相关 C++ 最小公倍数

include <iostream> using namespace std; int main() { int n1, n

本是古典何须时尚/ 2022年12月12日 13:52/ 0 赞/ 150 阅读

相关最小公倍数

include <iostream> include <cstdio> include <vector> include <map> i

╰+哭是因爲堅強的太久メ/ 2022年11月14日 10:24/ 0 赞/ 144 阅读

相关最小公倍数

![这里写图片描述][20160720212331293] 辗转相除法，不多说 include<stdio.h> int mud(int p,int q)

淩亂°似流年/ 2022年09月23日 14:57/ 0 赞/ 152 阅读

相关最大最小公倍数

问题描述已知一个正整数N，问从1~N中任选出三个数，他们的最小公倍数最大可以为多少。输入格式输入一个正整数N。输出格式输出一个整数，表示你找到的最小公倍数。

深藏阁楼爱情的钟/ 2022年08月02日 06:53/ 0 赞/ 215 阅读

相关求最小公倍数

/ 求最大公倍数 / include<stdio.h> include<stdlib.h> int getM

矫情吗；*/ 2022年07月16日 06:00/ 0 赞/ 216 阅读

相关 D - 最小公倍数

D - 最小公倍数 HPU专题训练（-1）GCD&&素筛&&快速幂\_\_\_\_\_D - 最小公倍数给定两个正整数，计算这两个数的最小公倍数。 I

谁践踏了优雅/ 2022年06月01日 07:54/ 0 赞/ 173 阅读

相关最小公倍数问题

问题：正整数A和正整数B 的最小公倍数是指能被A和B整除的最小的正整数值，设计一个算法，求输入A和B的最小公倍数。分析： > 求最小公倍数：公式法 > 两个数

Dear 丶/ 2022年03月09日 01:05/ 0 赞/ 222 阅读

相关最小公倍数

题意求1-20的最小公倍数。求两个数a，b的最小公倍数嘛，先取出其中较大的那个比如a，然后再用ka去试探能否被较小那个数整除，其中，k是从1开始的自然数 ka<a\

Myth丶恋晨/ 2022年01月27日 08:09/ 0 赞/ 226 阅读

相关最小公倍数

include<stdio.h> long long n; long long gcd( long long n,long long m )

你的名字/ 2021年11月02日 14:38/ 0 赞/ 302 阅读

相关最大公约数最小公倍数

最大公约数是两个及以上的数，能被所有的数整除的最大因子，就是这些数的最大公约数。举个栗子： 8的因子1,2,4,8 12的因子1,2,4,6,12 很明显他们的最

痛定思痛。/ 2021年09月20日 23:58/ 0 赞/ 414 阅读