n因子最小正整数解题报告_Here_is 有没有最小的正整数

【题目名称】：n因子最小正整数

【题目内容】：

Description

对于任意输入的正整数n,请编程求出具有n个不同因子的最小正整数m。例如：n=4，则m=6，因为6具有4个不同整数因子1，2，3，6；而且是最小的有4个因子的整数。

Input

本题有多组数据，每行一个数n(1≤n≤100000)。

Output

每组数据只输出一行为一个数字m

Sample Input

8

9

Sample Output

24

36

Source

Tju 1084

【题目简述】：求一个最小的有n个因子的正整数。

【题目考点】：高精度+因式分解+贪心（我的做法）

高精度+搜索（Maigo大牛的做法）

【题目分析】：

先说我的。

先介绍算数基本定理.

对于任意整数n，必能写成n=p1^a1* p2^a2*p3^a3* …… *pn^an;(p1<p2<p3<……<pn,{pi} 为质数集合)；

在这种情况下，

n的约数个数p=(a1+1)*(a2+1)*(a3+1)*……*(an+1);

因此，我们可以把n进行一次因式分解，得到n=b1*b2*b3*……*bn;(b1<b2<b3<……<bn);

然后要求的数m=p1^(b[n] - 1) * p2^(b[n-1] -1) * p3^(b[n-2] -1)* ……*pn^(b[1]-1);

貌似问题已经解决，但我发现这种思想里有一个致命的缺陷。

那就是

你无法保证得到的结果是最小的。

举个例子

输入 8

分解 8=2*2*2；

计算 2^1 * 3^1 * 5^1 =30;

然而，正确答案为 24 。

因为 8也可分解为这种形式： 8=2*4；

计算 2^3 * 3^1 =24;

所以，我们还需要一个判断函数，来消除这种差异！

假设 有一个数 n=b1*b2*b3*……*bi*……*bn；

如果把它分解成n=b1*b2*b3*……*(bj*bi)*……*b[i-1]*b[i+1]*……*bn，计算出来的结果比上式更小，

那一定满足这个条件：

p[n-i+1]^bi * p[n-j+1]^(bj)>p[n-j+1]^(bj*bi)(1)

约掉p[n-j+1]^(bj) 得：

p[n-i+1]^bi >p[n-j+1]^(bj*(bi - 1)); (2)

只要满足这个条件 就可一把bj赋为 bj*bi ，把bi赋为0，表示清除；

之后再计算就没有问题了。

O(∩_∩)o…哈哈

然后我把我的程序与Maigo的同时运行，自己输入一些大数据和小数据，基本上都合得上。

另外，这题要用高精度快速取幂。

【参考代码】：

我的：

//考虑到有人发现了程序对某些点有计算错误，暂时没空修正，目前来看这个思想是可以的，但可能需要用迭代多次的方法或者更为复杂的搜索方法来实现，我原来只用了一个二重循环明显太草率了

#include<iostream>

#include<cmath>

using namespace std;

intprime[]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71};//初始化prime。

intn,i,temp,a[1000]={0},j,ans[10000],c[10000],b[10000],t[10000];//a为记录质因数的数组，ans为最终答案。

void chenggao(int a[],int b[])//高精度乘高精度

{

int i,c[10000]={0},j;

for(i=1;i<=a[0];i++)

for( j=1;j<=b[0];j++)c[i+j-1]+=a[i]*b[j];

c[0]=a[0]+b[0];

for( i=1;i<=c[0];i++)

{

c[i+1]+=c[i]/10;

c[i]%=10;

}

while(c[c[0]]==0&&c[0]>0)c[0]--;

memcpy(a,c,sizeof(c));//保存当前结果。

}

void print(int a[])

{

if(a[0]==0){cout<<0<<endl;return;}

for(inti=a[0];i>0;i--)cout<<a[i];

cout<<endl;

}

double pro(int x,int y)//判断
{
double ans=x,t=x;

int c[100],i;c[0]=0;
while(y!=0){c[++c[0]]=y%2;y/=2;}
for( i=c[0]-1;i>=1;i--)
{
ans*=ans;
if(c[i]==1)ans*=t;
}
return ans;
}

void clean()//检查是否有非最优的搭配。

{

int i,j;

for( i=1;i<=a[0];i++)

for(j=a[0];j>i;j--)

if(a[i]*a[j]!=0)

if ( pro(prime[a[0]-i+1],a[i]-1) > pro(prime[a[0]-j+1],a[j]*(a[i]-1)) )//（2）式

{

a[j]*=a[i]; a[i]=0; break;

}

}

int main()

{

while(cin>>n)

{

memset(a,0,sizeof(a));

memset(ans,0,sizeof(ans));

for(i=2;i<=sqrt(n);i++)

while(n%i==0){a[++a[0]]=i;n/=i;}

if(n>1)a[++a[0]]=n;

//因式分解，详情请见http://blog.sina.com.cn/s/blog_61034ad90100eg3w.html；

clean();

ans[0]=ans[1]=1;

for(i=1;i<=a[0];i++)

if(a[a[0]-i+1]>0)

{ temp=a[a[0]-i+1]-1;

memset(c,0,sizeof(c));

memset(t,0,sizeof(t));

memset(b,0,sizeof(b));

while(temp!=0){c[++c[0]]=temp%2;temp/=2;}//快速取幂准备。

b[0]=t[0]=1; b[1]=t[1]=prime[i];

if(prime[i]/10>0)b[0]=t[0]=2,b[2]=t[2]=prime[i]/10;//赋初值。

for( j=c[0]-1;j>=1;j--)

{

chenggao(b,b);

if(c[j]==1)chenggao(b,t);//快速取幂主体。

}

chenggao(ans,b);//累乘结果。

}

print(ans);

}

return 0;

}

附：

maigo的题解，我选择，我喜欢，值得信赖。

program tju1084;

const

primes=16;

prime:array[1..primes]ofbyte=(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53);

base=10000;

type

bignum=array[-1..7525]of longint;

var

s,ans:array[0..primes]of longint;

n,ansp:longint;

anse:real;

a,b,c,d:bignum;

bool:boolean;

procedure search(n,p,limit:longint;e:real);

var

i:longint;

begin

if n=1then begin

if e<anse then begin ans:=s;anse:=e;ansp:=p;end;

exit;

end;

for i:=1to limit do

if n mod (i+1)=0 then begin

s[p]:=i;

search(n div (i+1),p+1,i,e+ln(prime[p])*i);

end;

end;

procedure mul(var a:bignum;b:byte);

var

i:longint;

begin

for i:=0to a[-1] do

a[i]:=a[i]*b;

for i:=0to a[-1] do begin

inc(a[i+1],a[i] div base);

a[i]:=a[i] mod base;

end;

ifa[a[-1]+1]>0 then inc(a[-1]);

end;

procedure hi_mul(var a,b,c:bignum);

var

i,j,k:longint;

begin

fillchar(c,sizeof(c),0);

for i:=0to a[-1] do

for j:=0 to b[-1] do begin

k:=i+j;

inc(c[k],a[i]*b[j]);

inc(c[k+1],c[k] div base);

c[k]:=c[k] mod base;

end;

c[-1]:=a[-1]+b[-1];if c[c[-1]+1]>0 theninc(c[-1]);

end;

procedure pow(var x,y:bignum;p:longint);

begin

if p=1then begin

fillchar(x,sizeof(x),0);x[0]:=prime[n];

end

elsebegin

pow(y,x,p shr 1);

hi_mul(y,y,x);

if odd(p) then mul(x,prime[n]);

end;

end;

procedure out(var a:bignum);

var

i:longint;

begin

write(a[a[-1]]);

fori:=a[-1]-1 downto 0 do

write(a[i] div 1000,a[i] div 100 mod 10,a[i] div 10 mod 10,a[i] mod10);

writeln;

end;

begin

repeat

read(n);

anse:=3e38;

search(n,1,n-1,0);

dec(ansp);

fillchar(a,sizeof(a),0);a[0]:=1;

for n:=1to ansp do begin

pow(c,d,ans[n]);

if odd(n) then hi_mul(a,c,b) else hi_mul(b,c,a);

end;

ifodd(ansp) then out(b) else out(a);

until seekeof;

end.