轻拍牛头

NC50554. 轻拍牛头

描述

今天是Bessie的生日，并且现在是聚会的游戏时间。Bessie让编号为 $1 \sim N$ 的N头奶牛围成一个圈坐（所以除了最后一头牛，第i头奶牛与第i-1和i+1头奶牛相邻，第N头奶牛和第N-1头与第1头奶牛相邻）。同时，FarmerJohn拿了个桶，在桶里装了十亿张小纸条，每张小纸条上写有某个范围在 $[1,10^6]$ 的整数。
接着，每头奶牛轮流从这个巨桶中抽取一个数 $A_i \ (1 \leq A_i \leq 10^6)$ （当然这些数没必要两两不同）。然后第i头奶牛走一圈，如果奶牛i手中的数字能够被奶牛 $j(j \neq i)$ 手中的数字整除，那么奶牛i会拍奶牛j的头。走完一圈后，奶牛i回到原来的位置。
奶牛们想让你帮他们计算，对于每头奶牛，它需要拍多少头奶牛的头？

输入描述

第一行包含一个整数N；
接下来第二到第N+1行每行包含一个整数。

输出描述

第一到第N行，第i行的输出表示第i头奶牛要拍打的牛数量。

示例1

输入:

输出:

说明:

第一头奶牛会拍第二、第三头奶牛，第二头牛不会拍任何奶牛的头，等等。

上次编辑到这里，代码来自缓存点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 68ms, 内存消耗: 9464K, 提交时间: 2019-08-21 21:05:36

#include<bits/stdc++.h>
using namespace std;
int a[100005],b[1000005],ans[1000005];
int main(){
	int n;
	scanf("%d",&n);
	memset(b,0,sizeof(b));
	memset(ans,0,sizeof(ans));
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		b[a[i]]++;
	}
	for(int i=1;i<=1000000;i++){
		if(b[i]){
			for(int j=i;j<=1000000;j+=i)
				ans[j]+=b[i];
		}
	}
	for(int i=1;i<=n;i++)
		printf("%d\n",ans[a[i]]-1);
	return 0;
}

C++ 解法, 执行用时: 316ms, 内存消耗: 9076K, 提交时间: 2021-11-08 20:21:38

#include<iostream>
using namespace std;
int a[1000010],b[1000010],c[1000010];
int main()
{
	int n,i,j;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>c[i];
		a[c[i]]++;
	}
	for(i=1;i<=1000010;i++)
		for(j=i;j<=1000010;j=j+i)
			b[j]+=a[i];
	for(i=1;i<=n;i++)
	  cout<<b[c[i]]-1<<endl;
	return 0;
}