[BZOJ 1607]轻拍牛头
转载请注明出处：http://danihao123.is-programmer.com/
噫……筛法
然而……人傻自带大常数
代码：
/**************************************************************
Problem: 1607
User: danihao123
Language: C++
Result: Accepted
Time:968 ms
Memory:9008 kb
****************************************************************/
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=100000,maxnumber=1000001;
int n,maxno;
int cot[maxnumber];
int A[maxn];
int cnt[maxnumber];
int main(){
register int i,j,maxv=0;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",&A[i]);
cnt[A[i]]++;
maxv=max(maxv,A[i]);
}
for(i=1;i<=maxv;i++)
if(cnt[i])
for(j=i;j<=maxv;j+=i)
cot[j]+=cnt[i];
for(i=0;i<n;i++)
printf("%d\n",cot[A[i]]-1);
return 0;
}
评论 (0)
