首页 > 代码库 > BZOJ1263 [SCOI2006]整数划分
BZOJ1263 [SCOI2006]整数划分
Description
从文件中读入一个正整数n(10≤n≤31000)。要求将n写成若干个正整数之和,并且使这些正整数的乘积最大。 例如,n=13,则当n表示为4+3+3+3(或2+2+3+3+3)时,乘积=108为最大。
Input
只有一个正整数: n (10≤n≤31000)
Output
第1行输出一个整数,为最大乘积的位数。 第2行输出最大乘积的前100位,如果不足100位,则按实际位数输出最大乘积。 (提示:在给定的范围内,最大乘积的位数不超过5000位)。
Sample Input
13
Sample Output
3
108
108
题解
由于对于$a > 1, b > 1$, 有$ab \geq a+b$(因为$ab-a-b=ab-a-b+1-1=(a-1)(b-1)-1\geq 1-1=0$),所以在答案中一定只存在$2,3$两个数(因为其它数都可以写成它们的和)。
那么,若$n>7$,那么答案中要么有三个以上的2,要么有两个以上的3,而$3^2=9>8=2^3$,所以答案一定有两个3.
那么ans*=9;n-=6;直到$n\leq 7$,这个时候直接查表。
附代码:
#include <cstdio> int len, ans[5050]; void mul(int x) { int i, c; for (i = 0, c = 0; i < len || c; ++i) { c = (ans[i] = ans[i] * x + c) / 10; ans[i] %= 10; } len = i; } const int e[] = {0, 1, 2, 3, 4, 6, 9, 12}; int main() { int n; scanf("%d", &n); len = 1, ans[0] = 1; while (n > 7) { mul(9); n -= 6; } mul(e[n]); printf("%d\n", len); for (int i = len - 1; ~i && i >= len - 100; --i) printf("%d", ans[i]); return 0; }
BZOJ1263 [SCOI2006]整数划分
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。