记录编号	566162	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI Online 2020 1st]最小环(民间数据)	最终得分	100
用户昵称	遥时_彼方	是否通过	通过
代码语言	C++	运行时间	0.421 s
提交时间	2021-11-02 19:15:06	内存使用	0.00 MiB

#include<bits/stdc++.h> 
#define ull unsigned long long
#define ll long long 
using namespace std;
int nc,mc;
ull n[200005];
ull ans[100002];
int p[100002];
ull pfh;
//bool cmp(ull x,ull y)
//{
//    return x>y;
//}
int gcd(int x,int y)
{
    while(x)
    {
        if(x<y) swap(x,y);
        x%=y;
    }
    return y;
}
int main()
{
    freopen("noi_online2020_ring.in","r",stdin);
    freopen("noi_online2020_ring.out","w",stdout);
    cin>>nc>>mc;
    for(int i=1;i<=nc;i++)
    {
        scanf("%llu",&n[i]);
        pfh+=(n[i]*n[i]);
    }
    sort(n+1,n+1+nc);
    int s1;
    int s2;
    int s3;
    int s4;
    ull l1,l2;
    for(int i1=1;i1<=mc;i1++)
    {
        scanf("%d",&s1);
//        cout<<endl;
        if(s1==0)
        {
            cout<<pfh<<endl;
            continue;
        }
        s2=gcd(nc,s1);
        if(p[s2]) 
        {
            printf("%llu\n",ans[s2]);
            continue;
        }
//        cout<<"ans:"<<ans<<endl;
        for(int i2=1;i2<=s2;i2++)
        {
            s3=nc/s2;
            s4=nc-(s3*i2);
            l1=n[s4+s3];
            l2=n[s4+s3-1];
            ans[s2]+=(l1*l2);
            s3-=2;
            while(s3)
            {
                if(l1<l2) swap(l1,l2);
                ans[s2]+=(l1*n[s3+s4]);
                l1=n[s3+s4];
                s3--;
            }
            if(nc/s2!=2) ans[s2]+=(l2*n[1+s4]);
//            cout<<"i2:"<<ans<<endl;
        }
        if(nc/s2==2) ans[s2]<<=1;
        printf("%llu\n",ans[s2]);
        p[s2]=1; 
    }
    return 0;
}     
//98108
//89450
//76939
//69222
//67045
//54982
//42661
//29015
//21448
//6403


//1/
//2
//3/
//4
//5/
//6
//7/
//8
//9/
//10