首页 > 代码库 > [质因数分解]UVa10791 Minimum Sum LCM
[质因数分解]UVa10791 Minimum Sum LCM
题目大意
输入整数n (1<=n<2^31)，求至少两个正整数，使得它们的最小公倍数为n，且这些整数的和最小，输出最小的和。
(LRJ小紫书P317页例题)
思考
看LRJ的分析没怎么看懂，随手搜了一篇题解。发现了一个讲的不错的，让我恍然大悟。
题解地址
首先假设我们知道了一系列数字a1，a2，a3……an，他们的LCM是n，那么什么时候他们是最优解呢，当他们两两互质的时候。
简单证明一下：
设两个正整数为a,b (a<=b) 其gcd(a,b)=n lcm(a,b)=m sum = a + b
如果n!=1(a,b不互质) 那么我们在m不变的情况下 优化一下 a = a / n
那么a变小后,sum必然减少。
那我们怎么保证两两互质呢？方法其实很简单，直接分解质因子。
所以我们已经得到了这个问题的解法
1.将一个数分解成质因子，将相同的因子乘起来作为一个处理后的因子
2.将处理后得到的多个因子直接相加就是答案
3.因为题目说只要需要两个数字，所以对于1和素数我们需要小心。对于素数，我们只能分解出一个因子就它自己，对于1一个因子都分解不出来（我们不把1当做因子），他们的答案都是n+1，因为只有1和n的LCM是n 。
#include <cstdio>#include <iostream>#include <cmath>typedef long long ll;ll f[233],Count,n,ans;void init(ll n){ ll m = (ll)sqrt(n+1); Count=0; for(ll i=2;i<=m && n>1 ;i++){ if(!(n%i)){ ll fac=1; while(!(n%i) && n>1){ fac*=i; n/=i; } f[Count++] = fac; //printf("Run\n"); } } if(n>1) f[Count++]=n;}int main(){ int Case=0; while(scanf("%d",&n) && n!=0){ ans=0; init(n); //printf("%d\n",Count); if(!Count || Count==1) ans=n+1; else for(int i=0;i<Count;i++) ans+=f[i]; printf("Case %d: %lld\n",++Case,ans); } return 0;}
[质因数分解]UVa10791 Minimum Sum LCM
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。