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

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+1;
long long n,m,a[N],ans1=0,ans2=0,t=0,ans[N];
bool b[N];
long long gcd(long long x,long long y)
{
    if(x%y==0)return y;
    else return gcd(y,x%y);
}
long long cmp(long long a,long long b)
{
    return a>b;
}
int main()
{
    freopen("noi_online2020_ring.in","r",stdin);
    freopen("noi_online2020_ring.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        ans1+=a[i]*a[i];
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n-2;i++)
    {
        ans2+=a[i]*a[i+2];
    }
    ans2+=a[1]*a[2];
    ans2+=a[n]*a[n-1];
    for(int i=1;i<=m;i++)
    {
        long long k;
        cin>>k;
        if(k==0||n==k)cout<<ans1<<endl;
        else if(gcd(n,k)==1)cout<<ans2<<endl;
        else
        {
            long long ans3=0,g=gcd(n,k);
            if(b[g])
            {
                cout<<ans[g]<<endl;
                continue;
            }
            for(int j=n/g;j<=n;j+=n/g)
            {
                for(int l=j-n/g+1;l<=j-2;l++)
                {
                    ans3+=a[l]*a[l+2];
                }
                ans3+=a[j-n/g+1]*a[j-n/g+2];
                ans3+=a[j]*a[j-1];
            }
            cout<<ans3<<endl;
            b[g]=1;
            ans[g]=ans3;
        }
    }
    return 0;
}