【BZOJ1607】【USACO2008 Dec】轻拍牛头

为啥这种智障题还要加个优化才能过啊

// <1607.cpp> - 08/11/16 20:01:59
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int gi(){
    int res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
const int MAXN=100010;
const int MAXM=1000001;
const int INF=1e9;
int a[MAXN],c[MAXM],ans[MAXM];
int main(){
    int n=gi(),mx=0;
    for(int i=1;i<=n;i++)c[a[i]=gi()]++,mx=max(mx,a[i]);
    for(int i=1;i<=mx;i++)
        if(c[i])for(int j=i;j<=mx;j+=i)ans[j]+=c[i];
    for(int i=1;i<=n;i++)printf("%d\n",ans[a[i]]-1);
    return 0;
}

// <1607.cpp> - 08/11/16 20:01:59

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int gi(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=100010;

const int MAXM=1000001;

const int INF=1e9;

int a[MAXN],c[MAXM],ans[MAXM];

int main(){

int n=gi(),mx=0;

for(int i=1;i<=n;i++)c[a[i]=gi()]++,mx=max(mx,a[i]);

for(int i=1;i<=mx;i++)

if(c[i])for(int j=i;j<=mx;j+=i)ans[j]+=c[i];

for(int i=1;i<=n;i++)printf("%d\n",ans[a[i]]-1);

return 0;

}