首页 > 代码库 > bzoj 1607 Patting Heads 轻拍牛头

bzoj 1607 Patting Heads 轻拍牛头

2024-08-18 00:34:10   217人阅读

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1607

题解：

　　题目似乎出错，应为“同时拍打所有所持纸条上的数字能被此牛所持纸条上的数字整除的牛的头（即不包括自己）”

　　有类似于桶排的思想，用bi记录数i的个数，用cj记录结果（即已知数集内j能整除的数的个数），接下来的运行过程类似于找某一范围内的质数：每找到i，将i的所有倍数j的cj++，输出时注意减一（除去自己本身）

 1 #include<cstdio>
 2 int n,a[100010],b[1000010],c[1000010],maxn;
 3 int max(int x,int y)
 4 {
 5     return x>y?x:y;
 6 }
 7 int main()
 8 {
 9     scanf("%d",&n);
10     for(int i=1;i<=n;i++)
11     {
12         scanf("%d",&a[i]);
13         b[a[i]]++;
14         maxn=max(maxn,a[i]);
15     }
16     for(int i=1;i<=maxn;i++)
17     {
18         if(b[i])
19         {
20             for(int j=i;j<=maxn;j+=i)
21             {
22                 c[j]+=b[i];
23             }
24         }
25     }
26     for(int i=1;i<=n;i++)
27     {
28         printf("%d\n",c[a[i]]-1);
29     }
30     return 0;
31 }

 

bzoj 1607 Patting Heads 轻拍牛头


联系
我们