CTNOWN - Bội số chung nhỏ nhất

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;

const int N = 350, M = 70;
bool pr[N+1];
vector<int> p;
long long f[N+1][M+1];

void eratos() {
    memset(pr, -1, sizeof pr); pr[0] = pr[1] = 0;
    for(int i = 2; i * i <= N; ++i) if(pr[i])
        for(int j = i + i; j <= N; j += i) pr[j] = 0;
    for(int i = 0; i <= N; ++i) if(pr[i]) p.push_back(i);
}

void solve() {
    for(int j = 0; j <= M; ++j) f[0][j] = 1;
    for(int i = 1; i <= N; ++i) 
        for(int j = 1; j <= M; ++j) {
            f[i][j] = max(f[i][j-1], f[i-1][j]);
            for(int d = p[j-1]; i >= d; d *= p[j-1]) f[i][j] = max(f[i][j], f[i-d][j-1] * d);
        }
}

int main() {
    eratos();
    solve();
    int tc, n; scanf("%d", &tc);
    while(tc--) {
        scanf("%d", &n);
        if(n <= N-3) printf("%lld\n", f[n][M]);
        else puts("14757354782123793840");
    }
    return 0;
}

Download