https://vjudge.net/problem/UVA-10791/origin
以上为题目来源Google翻译得到的题意：
一组整数的LCM（最小公倍数）定义为最小数，即
该集合的所有整数的倍数。有趣的是，可以表示任何正整数
作为一组正整数的LCM。例如12可以表示为1、12或
12、12或3、4或4、6或1、2、3、4等
在此问题中，您将得到一个正整数
N.您必须找出一组至少两个正整数，其LCM为N。
如果可能，您必须选择元素总和最小的序列。我们会很高兴
如果您仅打印此元素的总和
组。因此，对于N = 12，您应该将4 + 3 = 7打印为
4和3的LCM为12，而7则为最小值
总结。
输入值
输入文件最多包含100个测试用例。每个测试用例都由一个正整数N（1≤N≤2^ 31 − 1）组成。
输入在N = 0的情况下终止。
案件不予处理。最多可以有
100个测试用例。
输出量
每个测试用例的输出应由以“ Case＃：”开头的一行组成，其中＃是测试用例编号。它后面应该是问题陈述中指定的总和。看着那（这
输出为样本输入以获取详细信息。
翻译有一点语法问题，但是还是很好理解的。总结一下题目意思，就是给你一个N，你找到一组an使得n大于等于2. 且N 为an的最小公倍数，令an求和最小。
思路：
这道题最先要解决的就是，令求和最小这个要求，其实是什么？
再进一步解释就是，N可以拆解成多个因数连乘，那么到底是因数越多，越小越好，还是因数越少，越大越好？
很容易发现，如果是大的因数设为x，假设分解不彻底，那必有更小的bn使得bn之积等于x。
考虑到直接思考多个情况显然比较麻烦，以及刚刚说的x的事情，我们发现，多个因数组合成大因数会先从C（2，n）开始，那么不妨就先讨论，如果由一项变成拆成两项会怎么样？
即若令x=c*d，c+d大还是x大，即讨论 a+b与a*b大小的条件，
先给出一般应试办法，如果用数去试，试多几次，你会发现除了质数和1以外，a+b永远小于a*b，
那真的要计算证明有什么办法呢？以下是一些可能的思路（我自己没试过）和本人的办法（不一定很严谨）。
- 函数思路，令F（a，b）=a*b-（a+b），讨论二元函数F的零点，或令F（a，b）=（a+b）/ab -1，一样是讨论零点，
- 利用整数约束，解方程思路，令a+b=a*b，解该不定方程的正整数解，显然发现这是一个类似于，已知ax+by=c，“求逆元”的问题，即扩展欧几里得
- 利用不等式，求a+b与a*b大小关系
- 我的办法，虽然已经拆成了a，b两个，但是两个都还是动的，还是很麻烦呢
- 动手画图，解交点，很快发现，b=a/（a-1）为解。
- 当a大于等于1，这个解显然小于等于2，且从这个解之后，有y1图像恒在y2上方
- 得证，a+b小于等于a*b，若ab都不为1，取等条件是a=b且a=b=2
- 什么时候会是1，当且仅当质数、
那就干脆就再人为约束一下，令a不动b动，就有y1（b）=a*b，y2（b）=a+b，（a视为常数，大于等于1），比较俩函数在yOb图，交点出现的条件
好了，解完一个条件。但是完了吗？我一开始也以为完了，然后把N分解到能分解的极限，结果老WA，怎么回事？
看题才发现还没完，又有另一个问题，它要求这一组数的最小公倍数是N，那显然，N不能被分解到极限，那分解的极限在哪里呢？
我们要求分解的越多越好，N=Π(cn)^pn；(这里没有考虑分解项数一样的时候)
试一试，发现an都为某一质数的次方时似乎可以达到，个数最多，且刚好因为 ai^pi，aj ^pj 互相只有唯一且各不相同质因子，任意两两互质，所以N必为最大公约数
怎么证明？
如果只有两个数，a,b，此时LCM（a，b）=a*b/gcd（a，b），那么如果有n个数，LCM（an）=Πan/gcd（an），又，N=Πan；
（当且仅当，gcd（an）=1，即任意an都没有相同质因数的时候，才行，此时，当且仅当任意an都只有唯一质因子--即an为唯一质数的次方数的时候才满足，）（WA）
然后。。。在大佬的指正下，这个证明办法是有问题的。an是唯一质因数并不是唯一满足gcd（an）= 1 的条件，如果an取出的abcd令任意gcd（a，b）！=gcd（b，c），也可以
主要是这两种情况该怎么考虑, 即怎么理解分解程度--a+b小于a*b怎么往上推
- （a*1, b^2, c*1 ） （a*b，b*c，1*1）——（a*b，b*c）,（a*c，b^2，1*1）——（a*c，b^2）
- (a^2,b^2,c^2), (a*c^2 , b^2 , a )和 ( a*c, b, a*b) , 分解的项数一样,
彻底分解肯定得到的是质数，那，质数，有约束N大小，那显然可以先打表，再试除
只是又有一个前提，质数表打到N开根+1（2^16就可--65536）就行了，因为如果这些都搞不定N，那N一定筛不掉。
不过，必须注意这个办法筛出的素数并不能覆盖所有的输入值N，素数表是不完全的，
因此
- 要把没有被筛到的新素数另外检查，
- 或者筛到后面只剩下一个大于一但是又不在质数表的数加回去
而且小心N的输出值 可能会是 long long
另外要注意输入1时的条件，
还有之前an本身就是，唯一质因数次方的时候，这里又WA了好多次orz我真是太菜了
不含筛数：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <limits.h>
using namespace std;
typedef long long ll;
const int N=;
const int M=1e5;
bool x[M];//
int p[M];
int g=; //记录素数值
/*
void getprime1(int n) {//埃式筛法
memset(x,0,sizeof(x));
memset(p,0,sizeof(p));
g=0;//记录第几个素数--总数
//x[2]=0;
for(int i=2; i<=n; i++) {
if(x[i]==0) {
p[++g]=i;
//printf("%5d ",i);
for(int j=2; j*i<=n; j++) {
x[i*j]=1;
}
}
}
}
void getprime2(int n) {//Ola
memset(x,0,sizeof(x));
memset(p,0,sizeof(p));
g=0;//记录第几个素数--总数
//x[2]=0;
x[1]=0;//这题补一个要求
for(int i=2; i<=n; i++) {
if(x[i]==0) {
g++;
p[g]=i;
}
int t;
for(int j=1; j<=g&&(t=i*p[j])<=n; j++) {
x[t]=1;
}
}
}
*/ ll m=;
int main () { //getprime2(N);
int l=;
while(~scanf("%lld",&m)&&m) {
l++; //x[m]是不能直接用的,这点非常重要!!!!!
if(m==) {//否则会RE
printf("Case %d: 2\n",l);
} else {
//检查是不是没被覆盖的质数
//或者恰好是唯一质因数的次方数
int f=;
ll m1=m;
ll t=;
for(ll i=; i*i<=m1; i++) {//从2开始不然会一直m%1==0
ll q=;
while(m%i==) {
m/=i;
q*=i;
}
if(q>) {
//printf("%d: %lld\n",i,q);
t+=q;
f++;
//printf("%d\n",q);
} }
if(m!=) {
t+=m,f++;
}
if(f==)t++;
printf("Case %d: %lld\n",l,t);
}
}
//printf("\n\n%d\n",g); return ;
}
含筛数
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <limits.h>
using namespace std;
typedef long long ll;
const int N=;
const int M=1e5;
bool x[M];//
int p[M];
int g=; //记录素数值
/*
void getprime1(int n) {//埃式筛法
memset(x,0,sizeof(x));
memset(p,0,sizeof(p));
g=0;//记录第几个素数--总数
//x[2]=0;
for(int i=2; i<=n; i++) {
if(x[i]==0) {
p[++g]=i;
//printf("%5d ",i);
for(int j=2; j*i<=n; j++) {
x[i*j]=1;
}
}
}
}*/
void getprime2(int n) {//Ola
memset(x,,sizeof(x));
memset(p,,sizeof(p));
g=;//记录第几个素数--总数
//x[2]=0;
x[]=;//这题补一个要求
for(int i=; i<=n; i++) {
if(x[i]==) {
g++;
p[g]=i;
}
int t;
for(int j=; j<=g&&(t=i*p[j])<=n; j++) {
x[t]=;
}
}
} ll m=;
int main () { getprime2(N);
int l=;
while(~scanf("%lld",&m)&&m) {
l++;
ll t=;
//x[m]是不能直接用的,这点非常重要!!!!!
if(m==||(m<N&&x[m]==)) {//否则会RE
m++;
printf("Case %d: %lld\n",l,m);
} else {
//检查是不是没被覆盖的质数
int f=;
ll m1=m;//!!!
for(int i=; i<=g; i++) {
ll q=;
while(m%p[i]==) {
m/=p[i];
q*=p[i];
}
if(q>) {
t+=q;
f++;
//
//printf("%d: %lld\n",p[i],q);一直WA是因为没有把除完的数加上,
//如果除到最后都还大于1,说明不能被素数表上的完全筛完,
//最后剩下的一定是没有被筛完的质数,要加回去
//printf("%d\n",q);
}
}
//最后剩下的一定是没有被筛完的质数,要加回去
if(m!=) {
t+=m;
}
if(f>) {//不是质数
//printf("Case# %d: %lld\n",l,t);WA半天发现没有#
printf("Case %d: %lld\n",l,t);
} else {//是质数
t++;
printf("Case %d: %lld\n",l,t);
} }
}
//printf("\n\n%d\n",g); return ;
}
//结果发现不筛数更快2333
害！
(待续)