UVA 10791 Minimum Sum LCM（算术基本定理）

UVA 10791 Minimum Sum LCM（算术基本定理）

题意：给定一个n，就会产生几组数，每一组数的最小公倍数就是n，求这几组数中和最小的。

分析：根据算术基本定理，任何一个大于1的数都可以分解成几个素数的次幂相乘的形式。求几个数的和的最小，就要让每个数都是单独的素数次幂，因为他们的最小公倍数是几个数的标准分解式中每个素数的最高次幂组成的。

问题：一开始直接分解因数从2到n，但是T了。后来看题解，分解因数从2到sqrt(n)，在最后加上tn。因为如果一个数的素因子大于这个数的平方根，那么这个数除以这个素因子得到的另一个因子一定小于他的平方根，所以只到平方根就可以了。

超时代码：

#include #include #include #include using namespace std;typedef long long ll;ll n;int cas=0;int main(){ while (scanf("%lld", &n)!=EOF && n){ ll ans=0, tn=n; int flag=0; for (ll i=2; i<=n; i++){ ll t=0; if (tn%i==0){ flag++; t=1; while (tn%i==0){ t=t*i; tn/=i; } ans+=t; } } if (flag==0) //素数 ans=n+1; else if (flag==1) ans += 1; printf("Case %d: %lld\n", ++cas, ans); } return 0;}

AC代码：

#include #include #include #include using namespace std;typedef long long ll;ll n;int cas=0;int main(){ while (scanf("%lld", &n)!=EOF && n){ ll ans=0, tn=n; ll x=sqrt(n); int flag=0; for (ll i=2; i<=x; i++){ ll t=0; if (tn%i==0){ flag++; t=1; while (tn%i==0){ t=t*i; tn/=i; } ans+=t; } } if (flag==0) //素数 ans=n+1; //只有一个素数的次幂 || 还有因子(i到sqrt(n)节省时间,但是可能还有素数因子没算在内) else if (flag==1 || tn!=1) ans += tn; printf("Case %d: %lld\n", ++cas, ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。