首页 > 代码库 > 1607 [Usaco2008 Dec]Patting Heads 轻拍牛头
1607 [Usaco2008 Dec]Patting Heads 轻拍牛头
题目大意:n个数中,对其中每一个数,在其它(n-1)个数中有几个是他的因子。
题解:考虑到数Ai的范围不算太大,可以用一个桶统计1~MAX(Ai)每个数出现个数,然后把1~MAX的在MAX以内的倍数筛一遍即可。100000个数在1000000的桶里非常稀疏,忽略出现次数为0的数对时间效率十分重要。
代码:
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cctype> 5 #include<iostream> 6 using namespace std; 7 #define maxx 1000007 8 #define maxn 233333 9 #define ll long long 10 int a[maxn],num[maxx],n,MAX=0; 11 ll f[maxx]; 12 int qread() 13 { 14 char c;int s=0,t=1; 15 while (!isdigit(c=getchar())) if (c==‘-‘) t=-1; 16 do {s=s*10+c-‘0‘;} while (isdigit(c=getchar())); 17 return s*t; 18 } 19 int main() 20 { 21 n=qread(); 22 memset(num,0,sizeof(num)); 23 for (int i=1;i<=n;i++) a[i]=qread(),num[a[i]]++,MAX=max(a[i],MAX); 24 for (int i=1;i<=MAX;i++) 25 if (num[i]) for (int j=i;j<=MAX;j+=i) f[j]+=num[i]; 26 for (int i=1;i<=n;i++) printf("%lld\n",f[a[i]]-1); 27 return 0; 28 }
1607 [Usaco2008 Dec]Patting Heads 轻拍牛头
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。