2468. Patting Heads

单点时限: 5.0 sec

内存限制: 256 MB

It’s Bessie’s birthday and time for party games! Bessie has instructed the N (1 <= N <= 100,000) cows conveniently numbered 1..N to sit in a circle (so that cow i [except at the ends] sits next to cows i-1 and i+1; cow N sits next to cow 1). Meanwhile, Farmer John fills a barrel with one billion slips of paper, each containing some integer in the range 1..1,000,000.

Each cow i then draws a number A_i (1 <= A_i <= 1,000,000) (which is not necessarily unique, of course) from the giant barrel. Taking turns, each cow i then takes a walk around the circle and pats the heads of all other cows j such that her number A_i is exactly divisible by cow j’s number A_j; she then sits again back in her original position.

The cows would like you to help them determine, for each cow, the number of other cows she should pat.

输入格式

  • Line 1: A single integer: N

  • Lines 2..N+1: Line i+1 contains a single integer: A_i

输出格式

  • Lines 1..N: On line i, print a single integer that is the number of

other cows patted by cow i.

样例

Input
5
2
1
2
3
4
INPUT DETAILS:
The 5 cows are given the numbers 2, 1, 2, 3, and 4, respectively.
Output
2
0
2
1
3
OUTPUT DETAILS:
The first cow pats the second and third cows; the second cows pats no cows;
etc.

6 人解决,14 人已尝试。

10 份提交通过,共有 29 份提交。

7.6 EMB 奖励。

创建: 10 年,12 月前.

修改: 2 年,6 月前.

最后提交: 7 年,2 月前.

来源: USACO 2008 DEC

题目标签