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

Tác giả: ladpro98

Ngôn ngữ: C++

#include <bits/stdc++.h>
#define qword unsigned long long

const int N = 360;

using namespace std;

bool isPrime[N];
int P[N];
int nPrime;
qword dp[N][N];

void sieve() {
    memset(isPrime, 1, sizeof(isPrime));
    for (int i = 2; i * i < N; ++i) if (isPrime[i]) {
        for (int j = i * i; j < N; j += i)
            isPrime[j] = 0;
    }
    for (int i = 2; i < N; ++i)
        if (isPrime[i]) P[++nPrime] = i;
}

void update(int nxtI, int nxtJ, int i, int j, qword target) {
    if (dp[nxtI][nxtJ] < target)
        dp[nxtI][nxtJ] = target;
}

void preCalc() {
    for (int i = 0; i < N; ++i) dp[i][0] = 1;
    for (int i = 1; i <= nPrime; ++i) dp[P[i]][i] = P[i];
    for (int i = 0; i < N; ++i) for (int j = 0; j < nPrime && P[j] <= i; ++j) {
        update(i, j + 1, i, j, dp[i][j]);
        for (int p = 1; i + p < N; p *= P[j + 1])
            update(i + p, j + 1, i, j, dp[i][j] * p);
    }
}

void solve() {
    int n;
    cin >> n;
    qword ans = 0;
    for (int i = 0; i <= nPrime && P[i] <= n; ++i)
        ans = max(ans, dp[n][i]);
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    sieve();
    preCalc();
    int nTest;
    cin >> nTest;
    while (nTest--) solve();
    return 0;
}

Download