ECOO '19 R3 P1 - Chords

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 13.0s
Memory limit: 512M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Francesco has created his own piano-like instrument with N keys that each produce a unique frequency. One of his favourite things to do with the instrument is to play chords: a pair of keys where the frequency of one key is a multiple of the other. For example, the pair of frequencies (2, 4) is a pair, but (4, 6) is not. Francesco does not want to keep playing the same chords all the time, so he would like to know how many different chords can be played using his instrument. Two chords are different if one contains a key that the other does not. Can you help him figure out how many chords can be played?

Input Specification

The input will contain 10 datasets. Each dataset begins with a line containing an integer N (1 \le N \le 1\,000\,000), the number of keys. The next line contains N distinct integers F_i (1 \le F_i \le 1\,000\,000), the frequency of each key.

For the first 4 cases, N \le 1\,000.

Output Specification

For each dataset, output the number of chords that can be played.

Sample Input (Two Datasets Shown)

4
2 4 6 8
3
3 4 12

Sample Output

4
2

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org


Comments

There are no comments at the moment.