今天刷题时碰到这题一脸懵逼, 后来一看算法标签发现是数论就头都炸了. 想来想去只想到一点点规律但并不是很确定. 一看题解发现竟然用的是小学的知识解决.. 数学差的哭晕在地上qaq 因此重点记录数论类型的题目,下面是题目

题目描述
请你找出M个和为N的正整数,他们的乘积要尽可能的大。
输出字典序最小的一种方案。

输入输出格式

输入格式:
一行,两个正整数N,M
输出格式:
M个和为N的,乘积尽可能的大的正整数。

输入输出样例

输入样例#1:

6 3

输出样例#1:

2 2 2

说明

对于100%的数据,1N10^9,1M10^6

有人说这题只要懂得均值不等式(高中数学必修5)的定理就很容易做出来. 其实是学过,但是都还给高中老师了.因此特意去理解了下这是什么东东. 简单的说,当N个数的和M是相等的时候, N个数相等的时候, 他们的积是最大. 再换句话说, 和相等的两个数, 差值越小,积就越大.

(a+b)/2 >=√ab. 代入一些简单的数就能很容易看出, 例如当a和b分别为2和6 或者 4和4的时候 右边的值分别为√12和4

 

说了这么多只是想表达一个道理 几个数的和相等的时候,  当这些数都相等的时候, 他们的积是最大的

 

那么这道题目就能用这个定理解决, 用N / M求出平均数是多少. 但是存在一种情况就是, 不一定能整除. 这个时候想要求最大积的话, 那就尽量让数与数之间的差变的最小. 那么就把余数分别加到几个平均数里就好啦~ 但为了让差最小, 把余数分在其中的几个数 都加上1就好了.

 

所以题目的解决方法就是先求 N / M 再求N % M 因为要求从小到大输出, 因此先输出( N – (N % M) )个 N / M 然后再输出(N % M)个 (N / M) + 1

 

Code
[cc lang=”c”]#include
int main()
{
int n,m;
scanf(“%d %d”,&n,&m);
int t = n % m; //15 % 4 = 3
int a = n / m; //15 / 4 = 3

for(int i = t;i < m;i ++) { printf("%d ",a); } for(int i = 0;i < t;i ++) { printf("%d ",a + 1); } return 0; }[/cc]

Categories: OIer

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Related Posts

OIer

并查集学习总结

并查集学习总结 并查集在好早之前就想学了.. 虽然是一种比较简单的数据 Read more…

OIer

归并排序学习总结 & P1309

背景 之所以突然说到归并排序,是因为P1309这道题要用到&#8230 Read more…

OIer

队列和广度优先搜索

队列(queue) 队列是什么 队列是一种特殊的线性表. 是一种先进先 Read more…