首页 > 代码库 > UVA 10791 Minimum Sum LCM
UVA 10791 Minimum Sum LCM
| UVA - 10791 Minimum Sum LCM
Description  |  | Problem descriptions: System Crawler 2016-09-02    Initial |
uDebug题意：
求最小公倍数为n的数的和的最小值。
如12：(3,4),(2,6),(1,12)最小为7
题解：
唯一分解定理的模板
要想a1，a2，a3……an的和最小，要保证他们两两互质，只要存在不互质的两个数，就一定可以近一步优化
只是当n=1时，答案为2，而且可能会超，要用long long
AC代码：
#include<cstdio>#include<cmath>#include<vector>using namespace std;#define ll long long#define pir pair<ll,ll>vector<pir> f;ll n,cas; void deal(ll x){ f.clear(); ll m=floor(sqrt(x)+0.5); for(ll i=2;i<=m;i++){ if(x%i) continue; ll q=0; while(x%i==0) q++,x/=i; f.push_back(make_pair(i,q)); } if(x>1) f.push_back(make_pair(x,1));}ll fpow(ll a,ll p){ ll res=1; for(;p;p>>=1,a=a*a) if(p&1) res=res*a; return res;}void out(){ ll ans=0,size=f.size(); for(ll i=0;i<size;i++) ans+=fpow(f[i].first,f[i].second); if(size==1) ans++; printf("Case %lld: ",++cas); printf("%lld\n",ans);}int main(){ while(~scanf("%lld",&n)){ if(!n) break; if(n==1) {printf("Case %lld: 2\n",++cas);continue;} deal(n);out(); } return 0;}
UVA 10791 Minimum Sum LCM
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。