CTNOWN - Bội số chung nhỏ nhất
Tác giả: khuc_tuan
Ngôn ngữ: C++
#include <iostream>
#include <cstdio>
using namespace std;
const int COSO = 10000;
struct BigInt {
int a[20];
void assign(int x) {
a[0] = x;
for(int i=1;i<20;++i)
a[i] = 0;
}
void viet() {
for(int i=20-1;i>=0;--i)
if(a[i] > 0) {
printf("%d",a[i]);
for(int j=i-1;j>=0;--j)
printf("%04d",a[j]);
break;
}
}
BigInt opMul(int x){
BigInt b;
int nho = 0;
for(int i=0;i<20;++i) {
nho += a[i] * x;
b.a[i] = nho % COSO;
nho /= COSO;
}
return b;
}
int opCmp(BigInt b) {
for(int i=20-1;i>=0;--i) {
if(a[i] < b.a[i]) return -1;
if(a[i] > b.a[i]) return 1;
}
return 0;
}
};
const int MAXN = 355;
BigInt F[MAXN][300];
int prime[1000];
int main() {
int nprime = 0;
for(int i=2;i<300;++i) {
bool isprime = true;
for(int j=2;j*j<=i;++j)
if(i % j == 0) {
isprime = false;
break;
}
if(isprime)
prime[nprime++] = i;
}
for(int i=0;i<MAXN;++i) {
if(i < 2) F[i][0].assign(1);
else {
int z = 2;
while(2 * z <= i) z *= 2;
F[i][0].assign(z);
}
}
for(int p=1;p<nprime;++p) {
for(int i=0;i<MAXN;++i) {
F[i][p] = F[i][p-1];
int z = prime[p];
while(z <= i) {
BigInt tmp = F[i-z][p-1] .opMul( z );
if(F[i][p] .opCmp( tmp ) < 0) {
F[i][p] = tmp;
}
z *= prime[p];
}
}
}
int ntest, n;
scanf("%d",&ntest);
for(int test=0;test<ntest;++test) {
scanf("%d",&n);
F[n][nprime-1].viet();
printf("\n");
}
return 0;
}