A5610. 「一本通 6.2 练习 2」轻拍牛头
编程题
提高+/省选-
知识点
题目描述
**原题来自：USACO 2008 Dec. Silver**
今天是 Bessie 的生日，并且现在是聚会的游戏时间。Bessie 让编号为 $1\sim N$ 的 $N$ 头奶牛围成一个圈坐（所以除了最后一头牛，第 $i$ 头奶牛与第 $i-1$ 和 $i+1$ 头奶牛相邻，第 $N$ 头奶牛和第 $N-1$ 头与第 $1$ 头奶牛相邻）。同时，Farmer John 拿了个桶，在桶里装了十亿张小纸条，每张小纸条上写有某个范围在 $[1,10^6]$ 的整数。
接着，每头奶牛轮流从这个巨桶中抽取一个数 $A_i\ (1\le A_i\le 10^6)$（当然这些数没必要两两不同）。然后第 $i$ 头奶牛走一圈，如果奶牛 $i$ 手中的数字能够被奶牛 $j(j\neq i)$ 手中的数字整除，那么奶牛 $i$ 会拍奶牛 $j$ 的头。走完一圈后，奶牛 $i$ 回到原来的位置。
奶牛们想让你帮他们计算，对于每头奶牛，它需要拍多少头奶牛的头？
今天是 Bessie 的生日，并且现在是聚会的游戏时间。Bessie 让编号为 $1\sim N$ 的 $N$ 头奶牛围成一个圈坐（所以除了最后一头牛，第 $i$ 头奶牛与第 $i-1$ 和 $i+1$ 头奶牛相邻，第 $N$ 头奶牛和第 $N-1$ 头与第 $1$ 头奶牛相邻）。同时，Farmer John 拿了个桶，在桶里装了十亿张小纸条，每张小纸条上写有某个范围在 $[1,10^6]$ 的整数。
接着，每头奶牛轮流从这个巨桶中抽取一个数 $A_i\ (1\le A_i\le 10^6)$（当然这些数没必要两两不同）。然后第 $i$ 头奶牛走一圈，如果奶牛 $i$ 手中的数字能够被奶牛 $j(j\neq i)$ 手中的数字整除，那么奶牛 $i$ 会拍奶牛 $j$ 的头。走完一圈后，奶牛 $i$ 回到原来的位置。
奶牛们想让你帮他们计算，对于每头奶牛，它需要拍多少头奶牛的头？
输入格式
第一行包含一个整数 $N$；
接下来第二到第 $N+1$ 行每行包含一个整数 $A_i$。
接下来第二到第 $N+1$ 行每行包含一个整数 $A_i$。
输出格式
第一到第 $N$ 行，第 $i$ 行的输出表示第 $i$ 头奶牛要拍打的牛数量。
输入输出样例
输入 #1
5 2 1 2 3 4
输出 #1
2 0 2 1 3
说明/提示
对于全部数据，$1\le N\le 10^5$。