#10199. 「一本通 6.2 练习 2」轻拍牛头

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 1bentong

题目描述

原题来自: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 回到原来的位置。

奶牛们想让你帮他们计算,对于每头奶牛,它需要拍多少头奶牛的头?

输入格式

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

输出格式

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

样例

样例输入

5
2
1
2
3
4

样例输出

2
0
2
1
3

样例说明

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

数据范围与提示

对于全部数据, 1\le N\le 10^5