题解 SP3591 PATHEADS - Patting Heads

类似桶排

先看有多少头奶牛抽出这个数

再看这个数的奶牛能拍多少人的头（别忘了-1，自己不能拍自己）

最后根据输入输出

110ms

#include<bits/stdc++.h>

using namespace std;

bool f[1000001];

int n,a[1000001],in[1000001],v,maxv,ans[1000001];

void p()

{

    for(register int i=1;i<=1000000;i++)

    {

        if(!a[i]) continue;

        for(register int j=1;j<=1000000/i;j++)

        {

            ans[i*j]+=a[i];

        }

        ans[i]--;

    }

}

int main()

{

    cin>>n;

    for(register int i=1;i<=n;i++)

    {

        scanf("%d",&in[i]);

        a[in[i]]++;

    }

    p();

    for(register int i=1;i<=n;i++)

    {

        printf("%d\n",ans[in[i]]);

    }

    return 0;

}

巴特西

题解 SP3591 PATHEADS - Patting Heads

类似桶排

最新文章

热门文章