BZOJ1607: [Usaco2008 Dec]Patting Heads 轻拍牛头

题解:

思路非常朴素了吧...

令数值最大值为$mx$,则可以做到$O(mx\ln mx)$.

然后就是狗血的常数优化了.

代码:

#include<cstdio>
#include<cctype>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
 
inline int getc(){
    static const int L=1<<15;
    static char buf[L],*S=buf,*T=buf;
    if(S==T){
        T=(S=buf)+fread(buf,1,L,stdin);
        if(S==T)
            return EOF;
    }
    return *S++;
}
inline int getint(){
    int c;
    while(!isdigit(c=getc()));
    int x=c-'0';
    while(isdigit(c=getc()))
        x=(x<<1)+(x<<3)+c-'0';
    return x;
}
 
int a[100010],c[1000010],d[1000010];
int main(){
#ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
#endif
    int n;
    scanf("%d",&n);
    int i,j,mx=0;
    for(i=1;i<=n;++i){
        ++c[a[i]=getint()];
        mx=max(mx,a[i]);
    }
    for(i=1;i<=mx;++i)
        if(c[i]){
            for(j=i;j<=mx;j+=i)
                d[j]+=c[i];
        }
    for(i=1;i<=n;++i)
        printf("%d\n",d[a[i]]-1);
    return 0;
}