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;
}