首页 > 代码库 > UVa 10791 最小公倍数的最小和（唯一分解定理）
UVa 10791 最小公倍数的最小和（唯一分解定理）
https://vjudge.net/problem/UVA-10791
题意：
输入整数n，求至少两个正整数，使得它们的最小公倍数为n，且这些整数的和最小。
思路：
首先对n进行质因数分解，举个例子来说，12=2×2×3，最小和为7，也就是4和3，相同质因子必须放在一起，也就是说这里的2个2必须合在一起变成4，不然2和3会有更小的公倍数6。
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 #include <vector> 5 #include <queue> 6 #include <cmath> 7 using namespace std; 8 9 long long n;10 11 int main()12 {13 //freopen("D:\\input.txt", "r", stdin);14 int kase = 0;15 while (~scanf("%d", &n) && n)16 {17 int temp;18 int ret = 0;19 long long ans = 0;20 int m = sqrt(n + 0.5);21 for (int i = 2; i <= m && n > 1; i++)22 {23 if (n%i == 0)24 {25 temp = 1;26 while (n%i == 0)27 {28 temp *= i;29 n /= i;30 }31 ans += temp;32 ret++;33 }34 }35 if (n > 1)36 {37 ans += n;38 ret++;39 }40 while (ret < 2)41 {42 ans++;43 ret++;44 }45 printf("Case %d: %lld\n", ++kase, ans);46 }47 }
UVa 10791 最小公倍数的最小和（唯一分解定理）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。