首页 > 其他分享 >洛谷P1249最大乘积,数论找规律

洛谷P1249最大乘积,数论找规律

时间:2023-04-18 16:12:37浏览次数:47  
标签:洛谷 乘积 int P1249 Num 2004 题解 Last

最大乘积

题目描述

一个正整数一般可以分为几个互不相同的自然数的和,如 \(3=1+2\),\(4=1+3\),\(5=1+4=2+3\),\(6=1+5=2+4\)。

现在你的任务是将指定的正整数 \(n\) 分解成若干个互不相同的自然数的和,且使这些自然数的乘积最大。

输入格式

只一个正整数 \(n\),(\(3 \leq n \leq 10000\))。

输出格式

第一行是分解方案,相邻的数之间用一个空格分开,并且按由小到大的顺序。

第二行是最大的乘积。

样例 #1

样例输入 #1

10

样例输出 #1

2 3 5
30

这道题是数论加高精度,高精度倒好说,就是高精度乘法实现,模拟列竖式乘法,但是找出要乘的这几个数实属不容易,没学过数论,只能从题解中学怎么找规律
这里引用一下洛谷题解区赞数最高的题解

点击查看代码
我来帮大家理清一下这题的思路,并对其他题解做出解释和补充(我之前看的时候也比较懵)。
以下是本题的主要思路:
大家都清楚这题的意思,我们尽可能的把n分成更多份(都大于1)那样乘积最大。 (这里讲一下如果分出来的数可以重复,那么有时候并不是分出的份数越多越大,比如6,分成2,2,2不如分成3,3。但是不能重复的话就不存在这样的情况,大家可以想一下。) 以“6”为例,我们可以想到,我们先分出来一个2,然后再分出一个3......但是这样面临一个问题:“最后有余数怎么办”,比如“8”;分出来2,3还剩下3,没法再分出4,这时候怎么办呢?有的同学会想我把余数3都加到3身上,我们就分成了2和6,但是这样是最大的吗?(3和5才是最大的) 这时候我补充一下有一篇题解中所说:

“把余数分到大的数上比分到小的数上得到的乘积更大”。
实际不太准确,我们很容易证明出来如果能把数分到更小的数上,那么乘积更大(大家可以想想)。但是为什么最终是分到了大的数呢?就好比把6分成2,4,按照我们刚才的分法,先分出来了2和3最后余1,理论上我们把1给2得到的结果更大,但是我们不允许数重复,所以我们需要先把1给3,这样如果还剩下余数的话就分给2,所以当小的数被分配某个数后不会造成数的重复,那么优先给小的数分配,所以就像其他题解所说:

“从大数开始向前,依次分配1”。
所以对于8我们先分配出了2,3又余3,我们先分配1给3,得到2,4这时候2可以被分配,那么我们就分配给2一个1,得到3和4,这时候还余1,我们就分配给4,得到3,5。

这里我来解释一下点赞数最多的题解的思路。
以下为引用部分:
本题要先用简单的数论和贪心找到最优解的组成方法,再用高精度乘法求积。

以2004为例,由于把2004分拆成若干个互不相等的自然数的和的分法只有有限种,因而一定存在一种分法,使得这些自然数的乘积最大。

若1作因数,则显然乘积不会最大。把2004分拆成若干个互不相等的自然数的和,因数个数越多,乘积越大。为了使因数个数尽可能地多,我们把2004分成2+3…+n直到和大于等于2004。

若和比2004大1,则因数个数至少减少1个,为了使乘积最大,应去掉最小的2,并将最后一个数(最大)加上1。

若和比2004大k(k≠1),则去掉等于k的那个数,便可使乘积最大。

例如15:s=2+3+4+5+6刚好大于15,s-15=5,所以把5去掉。

又例如13:s=2+3+4+5刚好大于13,s-13=1,所以去掉2,并把5加1,即3 4 6。

大家可能觉得这个和我们刚才所讲的不太一样,为什么要减呢?怎么想到的呢?显然这样减,比我们一个个循环加更快。
我来帮大家推导一下:
我们分出来了2,3,4......n这n-1个数然后余数是K(1<=K<=n)。

1.如果K==n,我们需要进行两轮分配,意思是从n分配到2还剩下1,需要再回去把1分配给最大的数(也就是n+1)最终得到3,4,5......n+2这也就应对了上文题解中的情况2;
2.如果K<n,我们进行一轮分配就好因为我们的余数是K,那么分配到n+1-K就停止了,拿15举例,先分配出了2,3,4,5余1,我们分配到5就停止了,(n+1-K=5)。 对于上篇题解他先分配出2,3,4......n,n+1。因为我们分出来n-1个数余数是K,而分配出n+1后会造成数不够,还差n+1-K,那么这也就对应前两行我们推导出的结果,去掉n+1-K,就相当于分配到了n+1-K,应为n+1-K经过分配后变成了,n+2-K,这不就相当于去掉了吗。所以这相当于找规律了。

可以预知,在不允许重复的前提下一个数字分的项数越多(1除外,乘法中1不做贡献)(一般),其乘积一般会越大,因此我们期望将一个数从2连续分,直到分完整个数为止,显然许多数并不满足此情况,对于无法正好分完的数,我们可以将其分成两种情况

对于数 N,从2开始2,3,4....n-1,n,k,保证从2到n是连续数字,最后余数为k,很显然1<=k<=n,对于k,我们考虑将其均分在2-n的数里
具体分法以及解释可以参考上述题解的描述
当k==n时,从2-n这n-1个数,都可以分到一个1,最终剩下n-n-1=1,再重复这个步骤,正好将这多的1分到最后一个数上
可以参考如图
image
下面是AC代码

点击查看代码

#include<iostream>
using namespace std;
int Num[10001];
int main()
{
	int n;
	cin >> n;
	int Sum = 0;
	int Cnt = 0;
	//if (n < 5)
	//{
	//	if (n == 3)
	//		printf("1 2\n2");
	//	if (n == 4)
	//		printf("1 3\n3");
	//} 特判,小于5的数不太适合从2开始,不过数据没要求
//	else
	{
		for (int i = 2;; i++)
		{
			Sum += i;
			Num[Cnt++] = i;
			if (Sum == n)
				break;
			else if (Sum > n)
			{
				if (Sum == n + 1)
				{
					Num[0] = 1;
					Num[Cnt - 1] += 1;
				}
				else
				{
					Num[Sum - n - 2] = 1;
				}
				break;
			}
		}
		//以上是找数字部分,下面是高精度乘法部分
		int Anwser[500000] = { 0 };//这里空间够就用了int,否则是要用char的
		Anwser[0] = Num[0];//初始化第一位
		int Digit = 1;//答案数字的位数
		int Last = 0;//进位指标
		for (int i = 1; i < Cnt; i++)
		{
			for (int j = 0; j < Digit; j++)
			{
				int Temp = Anwser[j] * Num[i] + Last;
				Anwser[j] = Temp % 10;
				Last = Temp / 10;
			}
			while (Last)
			{
				Anwser[Digit++] = Last % 10;
				Last /= 10;
			}
		}
		int k = 0;
		while (Num[k] == 1)
			k++;//筛掉开始的1
		cout << Num[k++];
		for (; k < Cnt; k++)
			if(Num[k]!=1)
			cout << ' ' << Num[k];
		cout << endl;
		for (int l = Digit - 1; l >= 0; l--)
		{
			cout << Anwser[l];
		}
	}
	return 0;
}

标签:洛谷,乘积,int,P1249,Num,2004,题解,Last
From: https://www.cnblogs.com/WKWKSL/p/17330017.html

相关文章

  • 洛谷P5494 【模板】线段树分裂
    传送门  需要的前置知识:线段树合并。  感觉会了线段树合并这个就很简单,线段树分裂就是在把一颗权值线段树值域在[x,y]的区间分裂出来单独成一个线段树,那么我们只需要从新树q和旧树p的根节点一起走,如果走到当前p被[x,y]完全包含的路径就把p的编号给q,并且把p改为0就行了,注意......
  • java 递归方法 计算1-100之间的所有自然数的和 计算1-100之间所
    packageprectice;/***递归方法的使用**递归方法的定义:一个方法体内调用他自身**①方法递归包含了一种隐式循环,它会重复执行某段代码,但这种重发执行无须循环控制。*②递归一定要向已知方向递归,否则这种递归就变成了无穷递归,类似死循环。** 例1:计......
  • 洛谷 p1102 A-B数对
    题目背景出题是一件痛苦的事情!相同的题目看多了也会有审美疲劳,于是我舍弃了大家所熟悉的A+BProblem,改用A-B了哈哈!题目描述给出一串正整数数列以及一个正整数 C,要求计算出所有满足A−B=C 的数对的个数(不同位置的数字一样的数对算不同的数对)。输入格式输入共两行。......
  • 洛谷P7492 [传智杯 #3 决赛] 序列 题解 数列分块
    题目链接:https://www.luogu.com.cn/problem/P7492解题思路:分块。解题思路全部来自yzy1大佬的博客额外掌握技能:编译时加入-Wall参数。示例程序:#include<bits/stdc++.h>usingnamespacestd;constintmaxn=1e5+5;intn,m,blo,//n表示数列长度,m表......
  • 洛谷T226686 长度为2的子串
    题目描述给你一个长度为n 的由大写的英文字母组成的字符串,请你找出出现频率最高的长度为2的子串。输入格式包括两行。第一行是一个正整数n,表示字符串长度。第二行是长度为n的大写英文字母组成的字符串。(2<=n<=100)输出格式包括一行。一个长度为2的字符串,该字符串为输入......
  • 【剑指 Offer】 66. 构建乘积数组
    【题目】给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B[i]的值是数组A中除了下标i以外的元素的积,即B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。示例:输入:[1,2,3,4,5]输出:[120,60,40,30,24]来源:力扣(LeetCode)链接:https://leetc......
  • 【rmq】洛谷P7333
    题目:P7333[JRKSJR1]JFCA-洛谷|计算机科学教育新生态(luogu.com.cn)分析:用rmq处理出各个区间长度的最大值,然后在二分区间长度找到答案(最开始想的是开长度为n的数组,对位置i的数,分别找1-(i-1)和(i+1)-n中的离i最近满足条件的位置,然后更新结果,但一直wa,还没找到问题,存疑吧)代码:......
  • 洛谷 P3292 [SCOI2016]幸运数字
    https://www.luogu.com.cn/problem/P3292多次询问求一条链取若干点的最大异或和考虑一个集合的最大异或和可以求出线性基完成,两个集合的线性基可以合并,但是线性基并没有可减性,于是我们求lca的时候只能每次往集合里添加一条链,为了保证复杂度只能用倍增做。std::vector<i64>......
  • 数的乘积
    数的乘积考虑用除法解决这个问题。因为如果这些数的乘积超过了\(10^{18}\),那么用\(10^{18}\)依次除以这些数肯定存在一个时刻变为\(0\)。所以就可以在不使用__int128这类黑科技的情况下方便的判断。注意如果有一个数是\(0\)应该立刻停下输出\(0\),不然可能出现FloatPoi......
  • w1 洛谷T233243
      主要思路就是计算每一个长度为2的子串出现的次数,计数的同时用数组记录次数,打擂台找到出现次数最多的子串,首字符出现的位置就是数组的下标。最后输出出现最多的子串。代码如下:#include<bits/stdc++.h>usingnamespacestd;intcnt[100];intmain(){ intn,max=-1; ......