UVa 10791 (唯一分解) Minimum Sum LCM

题意:

输入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 }

代码君

时间: 12-11

UVa 10791 (唯一分解) Minimum Sum LCM的相关文章

UVA 10791 Minimum Sum LCM (数论)

LCM (Least Common Multiple) of a set of integers is defined as the minimum number, which is a multiple of all integers of that set. It is interesting to note that any positive integer can be expressed as the LCM of a set of positive integers. For exa

UVA - 10791 - Minimum Sum LCM (数论相关!)

题目链接:Minimum Sum LCM UVA - 10791 Minimum Sum LCM Time Limit:3000MS   Memory Limit:Unknown   64bit IO Format:%lld & %llu SubmitStatus Description  Minimum Sum LCM  LCM (Least Common Multiple) of a set of integers is defined as the minimum number, whic

Minimum Sum LCM(uva10791+和最小的LCM+推理)

L - Minimum Sum LCM Time Limit:3000MS     Memory Limit:0KB     64bit IO Format:%lld & %llu Submit Status Practice UVA 10791 题意:输入正整数n,<注意n=2^31-1是素数,结果是2^31已经超int,用long long,>找至少两个数,使得他们的LCM为n且要输出最小的和: 思路:既然LCM是n,那么一定是n的质因子组成的数,又要使和最小,那么就是ans+=[

Minimum Sum LCM(uva 10791)

题意(就是因为读错题意而wa了一次):给一个数字n,范围在[1,2^23-1],这个n是一系列数字的最小公倍数,这一系列数字的个数至少为2 例如12,是1和12的最小公倍数,是3和4的最小公倍数,是1,2,3,4,6,12的最小公倍数,是12和12的最小公倍数……………… 那么找出一个序列,使他们的和最小,上面的例子中,他们的和分别为13,7,28,24……显然最小和为7 /* 我们很容易可以发现,将n唯一分解之后,把所有质因数乘以次数加起来就行了.比如:12=2^2*3^1,那么ans=2^2

uva 10791 Minimum Sum LCM

#include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <stack> #include <set> #include <map> #include <string> #include <ma

UVA - 10791 Minimum Sum LCM(最小公倍数的最小和)

题意:输入整数n(1<=n<231),求至少两个正整数,使得它们的最小公倍数为n,且这些整数的和最小.输出最小的和. 分析: 1.将n分解为a1p1*a2p2--,每个aipi作为一个单独的整数时最优. 2.n为1时,len==0:n为素数时,len==1. #pragma comment(linker, "/STACK:102400000, 102400000") #include<cstdio> #include<cstring> #includ

[质因数分解]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 =

UVa10791 - Minimum Sum LCM

分析即为紫薯上的分析. 难点是发现当每个aipi作为一个单独的整数时才最优.. 答案就是将所有不同的 相同因子的积 相加即可 代码: #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<vector> #include<stack> #include<queue> #include<map> #in

Whu 1603——Minimum Sum——————【单个元素贡献、滑窗】

Problem 1603 - Minimum Sum Time Limit: 2000MS   Memory Limit: 65536KB   Total Submit: 623  Accepted: 178  Special Judge: No Description There are n numbers A[1] , A[2] .... A[n], you can select m numbers of it A[B[1]] , A[B[2]] ... A[B[m]]  ( 1 <= B[