CTNOWN - Bội số chung nhỏ nhất
Tác giả: hieult
Ngôn ngữ: C++
#include <stdio.h>
#include <math.h>
//#include <conio.h>
int main()
{
unsigned long long f[351][72];
int u[80],t=1;
u[1] = 2;
for(int i = 3;i<=355;i++)
{
int flag = 0;
for(int j = 1;;j++)
{
if(u[j]>sqrt(i))
break;
else if(i%u[j]==0)
{
flag=1;
break;
}
}
if(flag==0)
{
t++;
u[t]=i;
}
}
//printf("%d",u[t]);
for(int i = 1;i<=350;i++)
for(int j = 0;j<=t;j++)
f[i][j]=0;
for(int j = 0;j<=t;j++)
f[0][j] = 1;
for(int i = 1;i<=350;i++)
{
for(int j = 1;;j++)
{
if(u[j]>i)
break;
else
{
unsigned long long max = 0;
if(f[i-1][j]> max )
max = f[i-1][j];
if(f[i][j-1]>max)
max = f[i][j-1];
int t= u[j];
while(i-t>=0)
{
if(f[i-t][j-1]*t>max)
max = f[i-t][j-1]*t;
t=t*u[j];
}
f[i][j]=max;
}
}
}
int test,n;
scanf("%d",&test);
for(int ii = 1;ii<=test;ii++)
{
scanf("%d",&n);
if(n==1) printf("1\n");
else
{
unsigned long long Kq = 0;
for(int i = 1;i<=70;i++)
{
if(f[n][i]>Kq)
Kq=f[n][i];
}
printf("%llu\n",Kq);
}
}
//getch();
}