Description
n个人他们两两之间都是朋友,把他们分到m间房间中,每间房间中至少有一个人。
问分配后,朋友最少是多少对,最多是多少对。
Input
输入两个整数n和m,有(1<=m<=n<=10^9)。
Output
每行输出两个整数Kmin和Kmax。
Sample Input
6 3
Sample Output
3 6
思路:
猜例子大致得到当把所有人集中起来时(满足每个房间都有一个,其他集中起来),朋友的对数是最多的,而最少的就是平均分配出去。
最多的计算:
人数减去房数+1,剩下的N个人里CN,2,即n*(n-1)/2
最少的计算:
平均分配(当然不一定能完全平均),每个房间M个人,CM,2,即m*(m-1)/2,每个房间的加起来
#include<stdio.h>
int main(){
long long i,j,min,max,a,b;while(~scanf("%lld%lld",&a,&b)){
i=a/b;if(i==1){
min=a-b;max=(a-b+1)*(a-b)/2;}else{
min=(b-(a-i*b))*i*(i-1)/2+(a-i*b)*(i+1)*i/2;max=(a-b+1)*(a-b)/2;}printf("%lld %lld\n",min,max); }return 0;
}