#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn = 1000010;
__int64 sum[maxn] ;
__int64 num[maxn];
__int64 ans[maxn];
__int64 vis[maxn] ;
__int64 query;
__int64 n , q;
bool cmp1(__int64 a ,__int64 b)
{
return a > b;
}
int main()
{
while(~scanf("%I64d" ,&n))
{
for(int i = 1;i <= n;i++)
scanf("%I64d",&num[i]) ;
sort(num+1 , num+1+n , cmp1);
sum[0] = 0;
for(int i = 1;i <= n ;i++)
sum[i] = sum[i-1] + num[i];
memset(ans , 0 ,sizeof(ans)) ;
for(int k = 1;k < maxn; k++)
{
__int64 pos_s = 0 ;
__int64 pos_e = 1;
__int64 t = 0;
__int64 len = (__int64)k;
while(pos_s < n)
{
if(pos_e > n) pos_e = n;
ans[k] += (sum[pos_e] - sum[pos_s])*t ;
t++ ;
pos_s = pos_e;
pos_e += len;
len *= (__int64)k;
}
}
scanf("%I64d" , &q);
for(int i = 1;i <= q;i++)
{
scanf("%I64d" ,&query) ;
if(query > n) query = (__int64)n ;
printf("%I64d%c" ,ans[query] ,i == q?‘\n‘:‘ ‘);
}
}
return 0;
}
Codeforces Round #140 (Div. 1) Naughty Stone Piles 贪心
原文：http://blog.csdn.net/cq_pf/article/details/45082069
