D. The Millennium Prize Problems

Codeforces

IDCF10199D

Time15000ms

Memory1024MB

Difficulty—

English · Original

Formal · Original

Did you hear about the Millennium Prize Problems? They are seven problems in mathematics that were stated by the Clay Mathematics Institute on May 24, 2000. A correct solution for any of these problems results in a million dollar prize being awarded by the institute to the discoverer(s). Soliman, one of the ECPC judges came up with a new mathematics problem and claimed that it should be the eighth Millennium Prize Problem as he is pretty sure no one could solve it. Here's the problem: Given an array $A$ of length $N$ (the array can have duplicate values). What is the sum of all least common multiple (LCM) values for every pair of the array? More formally you need to calculate the following: $$ \sum_{i=1}^N \sum_{j=1}^N \text{LCM}(A_i, A_j)$$ Tefa, one of the ECPC judges suggested that we can add it in the problem set to see if someone can come up with a solution, so can you do it? The first line of the input contains a single integer $T$ the number of test cases, each test case consists of one line containing $N + 1$ space-separated integers, the first integer is the number $N$ the size of the array and the remaining integers are the elements of the array $A$, where $1 <= N <= 10^5$ and $1 <= A_i <= 10^5$. For each test case output the answer to the problem modulo $10^9 + 7$. ## Input The first line of the input contains a single integer $T$ the number of test cases, each test case consists of one line containing $N + 1$ space-separated integers, the first integer is the number $N$ the size of the array and the remaining integers are the elements of the array $A$, where $1 <= N <= 10^5$ and $1 <= A_i <= 10^5$. ## Output For each test case output the answer to the problem modulo $10^9 + 7$. [samples]

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case $ k \in \{1, \dots, T\} $: - Let $ n_k \in \mathbb{Z} $ denote the size of the array. - Let $ A_k = (a_{k,1}, a_{k,2}, \dots, a_{k,n_k}) $ be a sequence of positive integers, where $ 1 \le a_{k,i} \le 10^5 $. **Constraints** 1. $ 1 \le T \le \text{unspecified} $ (but input size implies feasible processing) 2. For each $ k \in \{1, \dots, T\} $: - $ 1 \le n_k \le 10^5 $ - $ 1 \le a_{k,i} \le 10^5 $ for all $ i \in \{1, \dots, n_k\} $ **Objective** For each test case $ k $, compute: $$ S_k = \left( \sum_{i=1}^{n_k} \sum_{j=1}^{n_k} \mathrm{LCM}(a_{k,i}, a_{k,j}) \right) \mod (10^9 + 7) $$

API Response (JSON)

{
  "problem": {
    "name": "D. The Millennium Prize Problems",
    "description": {
      "content": "Did you hear about the Millennium Prize Problems? They are seven problems in mathematics that were stated by the Clay Mathematics Institute on May 24, 2000. A correct solution for any of these problem",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 15000,
      "memory_limit": 1048576
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10199D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Did you hear about the Millennium Prize Problems? They are seven problems in mathematics that were stated by the Clay Mathematics Institute on May 24, 2000. A correct solution for any of these problem...",
      "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 $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ n_k \\in \\mathbb{Z} $ denote the size of the array.  \n- Let $ A_k = (a_...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments