I. What a Mess

Codeforces

IDCF10094I

Time2000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

Alex is a very clever boy, after all he is the son of the greatest watchmaker in Odin. One day, Alex was playing with some old watches and he found n gears, each gear has ai teeth in it. Alex likes to make beautiful pairs of gears, he thinks a pair of gears is beautiful if we attach the two gears together and spin the first gear exactly one rotation, then the other gear spins an integer number of rotations. For example a pair of _8_ and _4_ is beautiful, whereas a pair of _8_ and _5_ isn't, neither is pair of _4_ and _8_. Now Alex is curious, he wants to know how many beautiful pairs are there. Counting is not Alex's thing, so he asked you to help him. The first line of input contains one integer T: The number of test cases you need to process. Each test case consists of two lines. The first line is a single integer n: the number of gears Alex has. The second line contains n space separated integers ai: the number if teeth in the ith gear. 1 ≤ n ≤ 104 2 ≤ ai ≤ 106 For each testcase print a single integer: the number of distinct pairs that satisfy the problem statement. note that we consider two pair distinct when they differ by at least one gear. In the first sample the pairs are: _(4,8) , (4,12) , (6,12)_ ## Input The first line of input contains one integer T: The number of test cases you need to process.Each test case consists of two lines. The first line is a single integer n: the number of gears Alex has. The second line contains n space separated integers ai: the number if teeth in the ith gear.1 ≤ n ≤ 1042 ≤ ai ≤ 106 ## Output For each testcase print a single integer: the number of distinct pairs that satisfy the problem statement. [samples] ## Note note that we consider two pair distinct when they differ by at least one gear.In the first sample the pairs are: _(4,8) , (4,12) , (6,12)_

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case, let $ n \in \mathbb{Z} $ be the number of gears, and let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of integers representing the number of teeth on each gear. **Constraints** 1. $ 1 \leq T \leq 10^4 $ 2. For each test case: - $ 1 \leq n \leq 10^4 $ - $ 2 \leq a_i \leq 10^6 $ for all $ i \in \{1, \dots, n\} $ **Objective** For each test case, count the number of **unordered distinct pairs** $ \{a_i, a_j\} $ with $ i \ne j $ such that: $$ \frac{a_i}{a_j} \in \mathbb{Z} \quad \text{or} \quad \frac{a_j}{a_i} \in \mathbb{Z} $$ (i.e., one gear’s tooth count divides the other’s).

API Response (JSON)

{
  "problem": {
    "name": "I. What a Mess",
    "description": {
      "content": "Alex is a very clever boy, after all he is the son of the greatest watchmaker in Odin. One day, Alex was playing with some old watches and he found n gears, each gear has ai teeth in it. Alex likes t",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10094I"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Alex is a very clever boy, after all he is the son of the greatest watchmaker in Odin.\n\nOne day, Alex was playing with some old watches and he found n gears, each gear has ai teeth in it. Alex likes t...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case, let $ n \\in \\mathbb{Z} $ be the number of gears, and let $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of i...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments