例题 10-4 最小公倍数的最小和（Minimum Sum LCM, UVa10791）

本文主要是介绍例题 10-4 最小公倍数的最小和（Minimum Sum LCM, UVa10791），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接：https://vjudge.net/problem/UVA-10791
分类：基本数论
备注：唯一分解定理

又是唯一分解定理

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1e8+5;
ll n,kase,vis[maxn];
vector<ll>primes;
bool isPrime(ll x){ll m=sqrt(x+0.5);for(ll i=2;i<=m;++i)if(x%i==0)return false;return true;	
}
int main(void){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);while(~scanf("%lld",&n)&&n){if(n==1){printf("Case %lld: %lld\n",++kase,2);continue;	}if(isPrime(n)){printf("Case %lld: %lld\n",++kase,n+1);continue;	}ll ans=0,cnt=0,m=sqrt(n+0.5),v=n;for(ll i=2;i<=m;++i){ll tmp=1;while(n%i==0){n/=i; tmp*=i;}if(tmp!=1){++cnt; ans+=tmp; }}if(ans==v){//n=q1^a1printf("Case %lld: %lld\n",++kase,ans+1);continue;	}if(n!=1)ans+=n;//n=q1^a1*q2printf("Case %lld: %lld\n",++kase,ans);}return 0;	
}

这篇关于例题 10-4 最小公倍数的最小和（Minimum Sum LCM, UVa10791）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---