BZOJ 1263 整数划分
2024-08-31 02:28:01
Description
从文件中读入一个正整数\(n\)。要求将\(n\)写成若干个正整数之和,并且使这些正整数的乘积最大。 例如,\(n=13\),则当\(n\)表示为\(4+3+3+3\)(或\(2+2+3+3+3\))时,乘积\(=108\)为最大。
Input
只有一个正整数\(n\)。
Output
第1行输出一个整数,为最大乘积的位数。 第2行输出最大乘积的前\(100\)位,如果不足\(100\)位,则按实际位数输出最大乘积。 (提示:在给定的范围内,最大乘积的位数不超过\(5000\)位)。
Sample Input
13
Sample Output
3
108
Hint
\(10 \le n \le 31000\)
小学奥数结论题,尽可能地拆\(3\)即可,最后省\(4\)时拆成\(2\)与\(2\)(\(2 \times 2 > 3 \times 1\))。
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int n;
struct node
{
short a[10010],l;
node()
{
memset(a,0,sizeof(a));
l = 1;
}
friend inline node operator *(int x,node &y)
{
node ret; ret.l = y.l+1;
for (int i = 1;i <= y.l;++i)
{
ret.a[i] += y.a[i]*x;
ret.a[i+1] += ret.a[i]/10;
ret.a[i] %= 10;
}
if (ret.a[ret.l] == 0) ret.l--;
return ret;
}
inline void print()
{
printf("%d\n",l);
int t = 0;
for (int i = l;i >= 1;--i)
{
printf("%d",this->a[i]);
if (++t == 100) break;
}
}
}ans;
int main()
{
freopen("1263.in","r",stdin);
freopen("1263.out","w",stdout);
scanf("%d",&n); ans.a[1] = 1;
while (n)
{
if (n > 4) n -= 3,ans = 3*ans;
else if (n == 4) n-= 4,ans = 4*ans;
else ans = n*ans,n = 0;
}
ans.print();
fclose(stdin); fclose(stdout);
return 0;
}
最新文章
- 细说WebSocket - Node篇
- 剑指Offer:面试题33——把数组排成最小的数(java实现)(未完待续)
- mac 命令行批量删除.svn[转]
- Opencv CamShift+Kalman目标跟踪
- 通过imeMode禁用键盘只能输入数字
- Jquery UI的datepicker插件使用方法
- Linux安装Jdk,CentOS安装Jdk
- 为ASP.NET MVC应用程序读取相关数据
- startssl证书firefox支持配置
- Gym 100917C Constant Ratio 数论+暴力
- Entity Framework入门教程:什么是Entity Framework
- react native使用百度echarts显示图表
- PHP7 网络编程(五)进程间通信【待】
- android 5.0安装应用冲突问题
- MySQL 百万级分页优化(Mysql千万级快速分页)(转)
- Python3基础 try-指定except-as reason 捕获打开一个不存在的文件的时候,会产生OSError异常的示例
- [UE4]蓝图函数库小结
- [Flutter] Windows平台Flutter开发环境搭建(Andorid Studio)
- oracle什么时候须要commit
- 2018.9.20 Educational Codeforces Round 51