bzoj 1607 [Usaco2008 Dec]Patting Heads 轻拍牛头 （筛法）
http://www.lydsy.com/JudgeOnline/problem.php?id=1607
题意：n个数，求对于每个数来说，其他n-1个数中是它约数的数的个数。
思路：类似筛法，从小到大处理，数i对其所有倍数的数的答案有cnt[i]的贡献 。最后记得把自己是自己的约数的情况减掉。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年02月28日 星期日 01时06分35秒
4File Name :code/bzoj/1607.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=1E5+7;
34int n;
35int a[N];
36int cnt[N*10];
37int ans[N*10];
38int main()
39{
40 #ifndef ONLINE_JUDGE
41// freopen("code/in.txt","r",stdin);
42 #endif
43
44 ms(cnt,0);
45
46 cin>>n;
47 int mx = -1;
48 for ( int i = 0 ; i < n ; i++)
49 {
50 scanf("%d",&a[i]);
51 cnt[a[i]]++;
52 mx = max(mx,a[i]);
53 }
54
55 for ( int i = 1 ; i <= mx; i++)
56 if (cnt[i]) //类似筛法，对所有倍数都有贡献
57 for ( int j = 1 ; j*i <= mx ; j++)
58 ans[j*i]+=cnt[i];
59
60 for ( int i = 0 ;i < n ; i++)
61 printf("%d\n",ans[a[i]]-1);//减去自己是自己约数的情况
62
63
64
65
66
67 #ifndef ONLINE_JUDGE
68 fclose(stdin);
69 #endif
70 return 0;
71}