[BZOJ 1607]轻拍牛头

danihao123 posted @ 2016年5月15日 13:43 in 题解 with tags bzoj usaco 数学 数论 筛法 , 273 阅读
转载请注明出处: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;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter