注：从小雷那里搬的
Bobo has a point A in the n dimension real space RnRn, whose coodinate is (a1/m,a2/m,…,an/m)(a1/m,a2/m,…,an/m) where aiai and m are both integers. He wants to find another point P=(p1,p2,…,pn)P=(p1,p2,…,pn) meeting the following requirements.

* p1,p2,…,pn∈Rp1,p2,…,pn∈R. That is, they are real numbers.
* p1,p2,…,pn≥0p1,p2,…,pn≥0
* p1+p2+⋯+pn=1p1+p2+⋯+pn=1
* The (squared) Euclidean distance between P and A, which is ∥A−P∥22=∑ni=1(ai/m−pi)2‖A−P‖22=∑i=1n(ai/m−pi)2, is minimized.

It can be proved the minimum is always a rational number. Print the squared distance in fraction. Note to print an integer n as `n` instead of `n/1`.

输入描述: 

The input consists of several test cases and is terminated by end-of-file.
The first line of each test case contains two integers n and m.
The second line contains n integers a1,a2,…,ana1,a2,…,an.
* 1≤n≤1041≤n≤104 * 1≤m≤1031≤m≤103 * −m≤ai≤m−m≤ai≤m * The sum of n does not exceed 5×1055×105.

输出描述: 

For each test case, print a fraction which denotes the result.

题目大意：给定一个N维坐标系的点A（a1/m,a2/m,a3/m,...,an/m），寻找一个点P(p1,p2,p3,...,pn)满足p点的各坐标之和为1，且p1,p2,p3,...,pn > 0，使得A点到P点的欧几里得距离最小，其中A与P之间的欧几里得距离即为||A−p||22=∑ni=1(ai/m−pi)2||A−p||22=∑i=1n(ai/m−pi)2，求这个最小的欧几里得距离，若为分数则用分数形式表示。
首先将分母的m处理掉（记在分母），我们先将所有坐标放大m倍 ∑ni=1(pi)∑i=1n(pi) = m , A(a1,a2,a3,...,an),接下里我们转换一下问题，首先对A的坐标从大到小排个序

这是排序后的A的坐标们，我们现在需要确定P的坐标，也就是将-m（因为在欧几里得距离中A和P的坐标是直接相减关系）分配到这个图里，不难证明按照如下方法来分配效果最佳，

以下给出简答说明：我们要使得减去pi后的ai平方和最小，那么是ai中较大的数减小的收益一定比使较小的数（负的不就更小么，收益为负）变小的收益大，那么我们的第一次操作如图，将A1推平到与A2一样，为什么不继续往下推呢？因为我们接下来要连A2一起推！（否则A2也是较大不推血亏），同理，当我们的m剩余量还够时，我们就直接将A1，A2推平到A3,那么如图，加入当我们需要将A1,A2,A3,A4推平到A5时，我们的m不够用了，我们只需要将他们整体往下尽可能的推就行了，依然不难证明，参差不齐的推收益更小。
那么我们要做的就是维护一个前缀，并不断修改，前缀和m了，虽然这样很好懂，但其实这样，还是麻烦了！
上面说到了我们每次推平前i个是最优，这确实没错，但我们看看最后的状态，我们既然推平了前面的所有，那为何不一步推到位呢？我们只需要排序后记录前缀和，然后考虑到哪里前缀和减去m平不下去了，我们就推到哪里！
（这里应要求加上了样例3 10 1 -2 3 的情况，领会一下吧，(−8/3)2∗3∗/102=16/75(−8/3)2∗3∗/102=16/75）

代码如下： 

	#include<bits/stdc++.h>
#define Maxn 100008
using namespace std;
typedef long long ll;
ll n,m;
ll a[Maxn],sum[Maxn];
ll gcd(ll a,ll b){return(!b)?a:gcd(b,a%b);}
bool cmp(ll a,ll b){return a>b;}
int main(){
    while(scanf("%lld%lld",&n,&m)!=EOF){
        ll ansa,ansb,now=n;
        for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);
        sort(a+1,a+n+1,cmp);
        sum[0]=-m;
        for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
        for(int i=1;i<n;i++){
            if(sum[i]>a[i+1]*i){
                now=i;
                break;
            }
        }
        ansa=sum[now]*sum[now]*now;
        ansb=now*now;
        for(ll i=now+1;i<=n;i++)
                    ansa+=a[i]*a[i]*ansb;
        ansb*=m*m;
        ll gd=gcd(ansa,ansb);
        ansa/=gd,ansb /= gd;
        if(ansb==1||(!ansa))printf("%lld\n",ansa);
        else printf("%lld/%lld\n",ansa,ansb);
    }
}