您当前的位置: 首页 >  蓝桥杯

不牌不改

暂无认证

  • 0浏览

    0关注

    422博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

第二届蓝桥杯-最小公倍数问题

不牌不改 发布时间:2022-03-28 09:58:08 ,浏览量:0

题目

题目链接

题解

数学 + 高精度。

如果直接按照计算多个数连续计算最小公倍数,那么显然要经过高精度乘法、高精度除法,两个高精度过于麻烦了。

换个思路,我们将每个数都分解质因数,全部数的最小公倍数必然由分解得到的质因数相乘得到,而且构成最小公倍数的每种质因子的个数等于某个数分解得到该质因子最多的个数,举个例子:n=61,2,3,4,5,6分解质因子得到{1}, {2}, {3}, {2,2}, {5}, {2,3},那么构成这些数的最小公倍数的质因子2的个数应该为2,因为4存在两个质因子2,提供的2最多,我们为了保证最小公倍数能被4整除,所以最小公倍数的质因子2的数量就不能少于4的质因子数量,但是质因子3就只用取1个,因为3只有一个质因子36也只有一个质因子3。这就是为什么每个质因子都要取每个数数量最多的质因子个数的原因。

代码
#include
using namespace std;
int c[1000];

string mul (string s, int b) {
	string res = "";
	int m = s.size();
	reverse (s.begin (), s.end ());
	memset (c, 0, sizeof c);
	
	for (int i = 0;i = 0;i --)
	res += c[i] + '0';
	
	return res;
}

int n;
int cnt[110], res[110];
string ans = "1";

int main()
{
	cin >> n;
	for (int i = 2;i             
关注
打赏
1662186765
查看更多评论
0.0355s