USACO2008 Patting Heads筛数 oj24705

题目大意：

 N (1 < N < 100,000)头牛被编号为1-N，围坐成圈

每头牛都被画上数字A_i (1 ≤ A_i ≤ 1,000,000)，可能重复

逐个起来拍打 其他身上的数字是 自己身上的数字的约数 的牛包括本身的数字

 

Input

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains a single integer: A_i

Output

* Lines 1..N: On line i, print a single integer that is the number of other cows patted by cow i.

Sample Input

521234

Sample Output

20213

 

用普通的方法 数目太大会越界 结果RE

思路来自 http://blog.csdn.net/wnjxyk/article/details/38946819

类似线性筛数

#include <bits/stdc++.h> using namespace std; int main() { int n; scanf("%d",&n); int a[100005],flag[1000005],m=0,ans[1000005]; memset(flag,0,sizeof(flag)); memset(ans,0,sizeof(ans)); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); flag[a[i]]++; ///记录数字在牛身上出现与否及次数 m=max(m,a[i]); ///选出出现的最大的数 } for(int i=1;i<=m;i++) if(flag[i]) //如果出现 { for(int j=i;j<=m;j+=i) ///到最大数m前i的所有倍数j ans[j]+=flag[i]; ///所有倍数j的结果都加上i出现的次数 } for(int i=1;i<=n;i++) printf("%d\n",ans[a[i]]-1); ///输出结果需减掉其本身 return 0; } View Code

 

转载于:https://www.cnblogs.com/zquzjx/p/8359623.html

相关资源：JAVA上百实例源码以及开源项目