记录编号	572050	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI Online 2020 1st]最小环(民间数据)	最终得分	100
用户昵称	瞻远Daniel	是否通过	通过
代码语言	C++	运行时间	3.304 s
提交时间	2022-06-27 16:44:17	内存使用	0.00 MiB

#include<bits/stdc++.h>
using namespace std;
#define N 200000
long long n,m,sum;
long long a[N+4],d[N+4];
long long gcd(int a,int b)//最大公约数 
{
	int c=a%b;
	if(c==0)	return b;
	gcd(b,c);
}
queue<long long> q;
int main()
{
    freopen("noi_online2020_ring.in","r",stdin);
    freopen("noi_online2020_ring.out","w",stdout);//贪心greed
    long long i,j,k,l,t,tt,h[N+3];//l-loop
    cin>>n>>m;
    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a+0,a+n);
    a[n]=a[0];
    while(m--)
    {
        cin>>k;
        sum=0;
        if(k==0)
        {
            for(i=0;i<n;i++)
            {
                sum+=a[i]*a[i];
            }
            cout<<sum<<endl;
            continue;
        } 
        l=n/gcd(n,k);
//        printf(" %d\n",l);
        if(d[l])
        {
            cout<<d[l]<<endl;
            continue;
        }
        for(i=0;i<n;i+=l)
        {
            for(j=0;j<l;j++)
            {
                q.push(a[i+j]);
//                cout<<' '<<a[i+j];
//                sum+=a[i+j]*a[i+(j+1)%l];
            }
            t=q.front();
            j=0;
            while(!q.empty())
            {
                /*
                q.pop();
                sum+=t*q.top();
                tt=q.top();
                q.pop();
                sum+=t*q.top();
                t=tt;
                */
                h[j]=q.front();
                q.pop();
                if(!q.empty())
                {
                    h[l-j-1]=q.front();
                    q.pop();
                }
//                cout<<j<<' '<<l-j-1<<endl;
                j++;
            }
            h[l]=h[0];
            for(j=0;j<l;j++)
            {
//                cout<<h[j]<<' '<<h[(j+1)%l]<<endl;
                sum+=h[j]*h[j+1];
            }
//            cout<<endl;
        }
        d[l]=sum;
        cout<<d[l]<<endl;
    }
    return 0;
}//\
*knowing your code is no good, it fills you with determination