题目大意：求把一个整数(S)拆成若干数的和, 并且这些数的最小公倍数最大。输出最小公倍数对(m)取模的结果。
我们如果想使结果最大，肯定要尽量多的使用互质的数，因为互质的数的乘积就是最小公倍数，而不用除以这些数之间的最大公约数。那么全用素数和(1)不就行了吗？但是如果只想到这里的话就忘了一个问题，不仅不同的素数与素数之间是互质的，如果素数(a)与素数(b)不同，那么它们的幂(a^{k1})与(a^{k2})也是互质的。所以我们只要枚举出所有的不同素数(或(1))之间的组合，然后取结果的最大值就行了。因为每一个数都有用和不用两种情况，所以我们可以把每个素数都用(01)背包来处理。
在实现(01)背包的时候要注意一些细节。比如同一个素数的若干次幂要一起处理，而不能分成好几个物品分别处理，因为每个素数(以及它的幂)只能用一次，不然就不互质了，比如(2)和(4)。还有就是结果乘出来很大，题目也要求取模，但是如果取模的话不同组合之间的大小关系就不好比较了。这里我们可以对乘积取对数，而取模后的结果则存到另外一个数组中，这样既不影响不同组合之间的大小关系，也不会造成溢出。
const int maxn = 3e3+10;
int prime[maxn], ans[maxn], kase;
long double dp[maxn]; bool isprime[maxn];
void pri() {
for (int i = 2; i<maxn; ++i) {
if (!isprime[i]) prime[kase++] = i;
for (int j = 0; j<kase && prime[j]*i<maxn; ++j) {
isprime[i*prime[j]] = true;
if (!(i%prime[j])) break;
}
}
}
int main(void) {
int n, mod; pri();
while(~scanf("%d%d", &n, &mod)) {
for (int i = 0; i<=n; ++i) dp[i] = 0, ans[i] = 1;
for (int i = 0; i<kase && prime[i]<=n; ++i)
for (int j = n; j>=prime[i]; --j)
for (int k = prime[i]; k<=j; k *= prime[i])
if (dp[j] < dp[j-k] + log2(k)) {
dp[j] = dp[j-k] + log2(k);
ans[j] = ans[j-k]*k%mod;
}
printf("%d
", ans[n]);
}
return 0;
}