首页 > 代码库 > UVa 10791 (唯一分解) Minimum Sum LCM

UVa 10791 (唯一分解) Minimum Sum LCM

2024-08-07 20:49:03   216人阅读

题意：

输入n，求至少两个正整数，使得这些数的最小公倍数为n且和最小。

分析：

设n的分解式为，很显然单独作为一项，和最小。

这里有两个小技巧：

  • 从2开始不断的除n，直到不能整除为止。这样就省去了素数判断的问题，而且缩短了代码量。因为最开始把所有n的2的因数都出去了，后面便不会出现n % 4 == 0的情况，这样除n的都是素数。
  • 从2除n一直到sqrt(n)，如果n不为1，则此时除“剩下”的就是n最大的质因数。减少循环次数。
 1 #include <cstdio> 2 #include <cmath> 3  4 typedef long long LL; 5  6 int main(void) 7 { 8     int n, kase = 0; 9     while(scanf("%d", &n) == 1 && n)10     {11         LL ans = 0;12         int m = sqrt(n + 0.5);13         int pcnt = 0;14         15         if(n == 1)16         {17             printf("Case %d: 2\n", ++kase);18             continue;19         }20         21         for(int i = 2; i <= m; ++i)22         {23             if(n % i == 0)24             {25                 pcnt++;26                 int temp = 1;27                 while(n % i == 0)28                 {29                     n /= i;30                     temp *= i;31                 }32                 if(temp > 1) ans += temp;33             }34         }35         if(n > 1)36         {37             pcnt++;38             ans += n;39         }40         if(pcnt <= 1) ans++;41         42         printf("Case %d: %lld\n", ++kase, ans);43         44     }45     46     return 0;47 }
代码君

 

UVa 10791 (唯一分解) Minimum Sum LCM


联系
我们