PATHEADS  Patting Heads
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 i1 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.
Input
 Line 1: A single integer: N.
 Lines 2..N+1: Line i+1 contains a single integer: A_{i}.
Output
 Lines 1..N: On line i, print a single integer that is the number of other cows patted by cow i.
Example
Input: 5 2 1 2 3 4 Output: 2 0 2 1 3
The first cow pats the second and third cows; the second cows pats no cows; etc.
hide comments
lovro_nidogon1:
20220703 13:04:43
Ez 

holmesherlock:
20170403 19:33:17
easy one :)


vengatesh15:
20170222 16:20:39
Finally removed from my todolist 

Piyush Kumar:
20160608 11:37:56
There is no need of sorting in this! 

anon:
20150617 19:07:11
Sieve + STL =AC 
Added by:  Neal Wu 
Date:  20081226 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL 
Resource:  USACO Dec 2008 