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;
n因子最小正整数解题报告_Here_is 有没有最小的正整数
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.

  

爱华网本文地址 » http://www.413yy.cn/a/25101013/167237.html

更多阅读

有没有驱蚊子的小妙招? 驱蚊小妙招

综合治理,效果持久 要从源头上消除蚊子。最好是把蚊子容易滋生和繁殖的地方打扫干净,特别是静水和阻塞的水槽。家中容器中的积水不要放置过长,发现蚊子幼虫,要用开水烫死。住在底楼要注意地漏和下水管道口。疏通下水道,排水口设防蚊闸。

声明:《n因子最小正整数解题报告_Here_is 有没有最小的正整数》为网友蜜糖融化我的心分享!如侵犯到您的合法权益请联系我们删除