[USACO08DEC] Patting Heads S

题目描述

It's Bessie's birthday and time for party games! Bessie has instructed the N (1 <= N

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.

5 
2 
1 
2 
3 
4 

2 
0 
2 
1 
3 

提示

The 5 cows are given the numbers 2, 1, 2, 3, and 4, respectively.

The first cow pats the second and third cows; the second cows pats no cows; etc. 标签: P2926|2008|USACO|素数判断,质数,筛法

来源

P2926|[USACO08DEC] Patting Heads S