A20908. 拆分
填空题
困难
知识点
题目描述
拆分
题目描述
小A想将正整数n拆分成若干个正整数之和，并最大化拆分后的正整数之积。小A希望你帮他计算出拆分后正整数之积的最大值。由于答案可能很大，你只需要求出答案对109取模的结果。
形式化地，n的拆分是满足a1十...十ak=n的若干个正整数a1,...,ak，其中1≤k≤n。你需要求出n的所有拆分中a1×...×an的最大值对109取模的结果。
输入格式
第一行，一个正整数t，表示数据组数。
对于每组数据：一行，一个整数n，表示给定的正整数。
输出格式
对于每组数据：输出一行，一个整数，表示n拆分后正整数之积的最大值对109取模的结果。
样例
输入样例
3
5
8
100输出样例
6
18
755407364数据范围
对于40%的测试点，保证n≤50。
对于所有测试点，保证1≤t≤104，1≤n≤106。
参考答案
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1e6 + 5;
const int mod = 1e9;
const double ln2 = log(2);
const double ln3 = log(3);
int f[N];
double lnf[N];
int main() {
f[0] = f[1] = 1;
for (int i = 0; i < N; i++) {
if (i + 2 < N && lnf[i] + ln2 > lnf[i + 2]) {
lnf[i + 2] = lnf[i] + ln2;
f[i + 2] = 2LL * f[i] % mod;
}
if (i + 3 < N && lnf[i] + ln3 > lnf[i + 3]) {
lnf[i + 3] = lnf[i] + ln3;
f[i + 3] = 3LL * f[i] % mod;
}
}
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
printf("%d\n", f[n]);
}
return 0;
}
上一题
下一题