【bzoj1263】[SCOI2006]整数划分 高精度
整数 划分 高精度
2023-09-11 14:22:40 时间
题目描述
从文件中读入一个正整数n(10≤n≤31000)。要求将n写成若干个正整数之和,并且使这些正整数的乘积最大。 例如,n=13,则当n表示为4+3+3+3(或2+2+3+3+3)时,乘积=108为最大。
输入
只有一个正整数: n (10≤n≤31000)
输出
第1行输出一个整数,为最大乘积的位数。 第2行输出最大乘积的前100位,如果不足100位,则按实际位数输出最大乘积。 (提示:在给定的范围内,最大乘积的位数不超过5000位)。
样例输入
13
样例输出
3
108
题解
高精度
首先根据某小学奥数理论,如果n%3==0,则全拆成3;如果n%3==1,则拆出来一个4,其余全拆成3;如果n%3==2,则拆出来一个2,其余全拆成3.
然后高精度乘低精度就好了。
由于有位数限制,所以比较懒没有压位,可能会慢点。
#include <cstdio> #include <cstring> struct data { int len , num[5010]; data() { len = 0 , memset(num , 0 , sizeof(num)); } data operator=(const int a) { len = 1 , num[0] = a; return *this; } data operator*(const int a)const { data t; int i; for(i = 0 ; i < len ; i ++ ) t.num[i] += num[i] * a , t.num[i + 1] += t.num[i] / 10 , t.num[i] %= 10; t.len = len + (bool)t.num[len]; return t; } void output() { printf("%d\n" , len); int i; for(i = len - 1 ; i >= 0 && i >= len - 100 ; i -- ) printf("%d" , num[i]); printf("\n"); } }ans; int main() { int n , i; scanf("%d" , &n); ans = (n + 1) % 3 + 2; for(i = 1 ; i <= (n - 2) / 3 ; i ++ ) ans = ans * 3; ans.output(); return 0; }
相关文章
- 整数划分问题--DFS
- Newtonsoft.Json C# Json序列化和反序列化工具的使用、类型方法大全 C# 算法题系列(二) 各位相加、整数反转、回文数、罗马数字转整数 C# 算法题系列(一) 两数之和、无重复字符的最长子串 DateTime Tips c#发送邮件,可发送多个附件 MVC图片上传详解
- 如何从40亿整数中找到不存在的一个 webservice Asp.Net Core 轻松学-10分钟使用EFCore连接MSSQL数据库 WPF实战案例-打印 RabbitMQ与.net core(五) topic类型 与 headers类型 的Exchange
- Java之戳中痛点 - (6)避免类型自动转换,例如两个整数相除得浮点数遇坑
- 基于 97整数小数变换的图像压缩算法的FPGA实现,verilog编程(6800+字)
- C# TextBox 限制输入一点范围内的整数并有提示超过所限定范围的整数
- TextBox控件输入一个整数转为整数变量使其代码中调用输入的值
- C/C++ 实现 a/b 向上取整和向下取整,其中a > 1, b > 1且 a、b均为整数
- shell整数测试
- 力扣解法汇总1805. 字符串中不同整数的数目
- 力扣解法汇总13-罗马数字转整数
- 圆心在(0,0)坐标半径为大整数的一个圆,求圆周上有多少坐标为整数的点
- 分析轮子(三)- 十进制整数怎么变成无符号二进制的整数的
- 191、【动态规划】AcWing —— 900. 整数划分:完全背包解法+加减1解法(C++版本)
- 华为OD机试 -整数对最小和(Java) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 -用连续自然数之和来表达整数(Java) | 机试题+算法思路+考点+代码解析 【2023】
- java之整数的分解可以理解为倒序输出
- 整数划分问题(仅仅显示种类数)
- js 输入整数
- Java //PP2.2 编写一个应用程序,读取三个整数,然后打印输出它们的平均值
- D:大整数的加减乘除