比赛 EYOI暨SBOI暑假快乐赛3rd 评测结果 WWWWWWAWAWWWWWWWWWWW
题目名称 最小环(民间数据) 最终得分 10
用户昵称 op_组撒头屯 运行时间 0.335 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2022-06-27 11:54:19
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200000+5;
int n,m;
ll a[N];
ll ans[N]={0};
int b[N]={0};
void pre(int p){
    int t=n/p,c=2,d=0;
    while(c<=t){
        b[++d]=a[c];c+=2;
    }
    if (t%2==0)c-=3;
    else c--;
    while(c>=1){
        b[++d]=a[c];c-=2;
    }
    ll sumc=b[t]*b[1],sumj=b[t]+b[1];
    for (int i=1;i<t;i++){
        sumc+=b[i]*b[i+1];
        sumj+=b[i]+b[i+1];
    }
    ans[p]=p*sumc+(p-1)*p/2*t*sumj+p*(p-1)*(2*p-1)/6*t*t*t;
    if (t==2)ans[p]/=2;
    return ;
}
int gcd(int x,int y){
    if (y==0)return x;
    return gcd(y,x%y);
}
int main(){
    freopen ("noi_online2020_ring.in","r",stdin);
    freopen ("noi_online2020_ring.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        ans[0]+=a[i]*a[i];
    }
    sort(a+1,a+n+1);
    for (int i=1;i<=n/2;i++){
        if (n%i==0){
            pre(i);
        }
    }
    for (int i=1;i<=m;i++){
        int k;scanf("%d",&k);
        if (k==0){
            printf("%lld\n",ans[k]);
            continue;
        }
        int g=gcd(k,n);
        printf("%lld\n",ans[g]);
    }
    return 0;
}