题解 [Usaco2008 Dec]Patting Heads 轻拍牛头

题目传送门

披着数论外衣的乱搞题

把每一个数都标记一下，然后直接搞就可以了。

Code

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 1e5+1;
const int A = 1e6+1;

int n,ans;
int a[N];
int cnt[A];
int t[A];
int maxx;

inline void readx(int &x)
{
    x=0;
    int s=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            s=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    x*=s;
}

int main()
{
    readx(n);
    for(int i=1;i<=n;++i)
    {
        readx(a[i]);
        ++cnt[a[i]];
        maxx=max(maxx,a[i]);
    }
    for(int i=1;i<=maxx;++i)
    {
        if(cnt[i])
            for(int j=i;j<=maxx;j+=i)
                t[j]+=cnt[i];
    }
    for(int i=1;i<=n;++i)
    {
        printf("%d\n",t[a[i]]-1);
    }
    return 0;
}

/*
5 
2 
1
2
3
4

*/

[Usaco2008 Dec]Patting Heads

原文：https://www.cnblogs.com/oierwyh/p/11342088.html