C. Two Cats

Codeforces

IDCF10187C

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

After your death, you're sent to a mysterious room. There are two cats guarding two doors, one leading to heaven of AC problems and the other leading to hell NO. One cat likes all divisors of an integer a, a being the product of n integers v1, v2, ..., vn. The other cat likes all integers with exactly b divisors. You were asked to count the number of integers that satisfy both cats. If you count correctly, you may go to the heaven of AC problems, full of balloons, otherwise you're sent to hell NO. As the answer can be quite large, print the remainder of this number modulo 109 + 7. The first line of the input contains two integers b (1 ≤ b ≤ 103) and n (1 ≤ n ≤ 103). The following line contains n space separated integers v1, v2, ..., vn (2 ≤ vi ≤ 1012) whose product is a. Output a single integer - the number of integers that satisfy both cats modulo 109 + 7. ## Input The first line of the input contains two integers b (1 ≤ b ≤ 103) and n (1 ≤ n ≤ 103).The following line contains n space separated integers v1, v2, ..., vn (2 ≤ vi ≤ 1012) whose product is a. ## Output Output a single integer - the number of integers that satisfy both cats modulo 109 + 7. [samples]

**Definitions** Let $ G = (V, E) $ be an undirected multigraph where: - $ V = \{1, 2, \dots, N\} $ is the set of islands. - $ E = E_{\text{exist}} \cup E_{\text{add}} $, with $ |E_{\text{exist}}| = M $ (existing bridges) and $ |E_{\text{add}}| = K $ (candidate bridges to add). Let $ d(v) $ denote the degree of vertex $ v \in V $ in the graph $ G' = (V, E_{\text{exist}} \cup E') $, where $ E' \subseteq E_{\text{add}} $ is the set of added bridges. **Constraints** 1. $ 1 \le N \le 10^5 $, $ 0 \le M \le 10^5 $, $ 0 \le K \le 10^5 $. 2. Each bridge is an unordered pair $ \{a, b\} $ with $ a, b \in V $, $ a \ne b $. 3. Multiple edges between same pair allowed. 4. The graph $ (V, E_{\text{exist}}) $ is connected. **Objective** Determine if there exists a subset $ E' \subseteq E_{\text{add}} $ such that in the graph $ G' = (V, E_{\text{exist}} \cup E') $: - Every vertex has even degree (i.e., $ d(v) \equiv 0 \pmod{2} $ for all $ v \in V $), - and a closed Eulerian trail exists (which is guaranteed if the graph is connected and all degrees are even). If such $ E' $ exists, output: - "YES", - $ R = |E'| $, - the $ R $ edges in $ E' $. Otherwise, output "NO".

API Response (JSON)

{
  "problem": {
    "name": "C. Two Cats",
    "description": {
      "content": "After your death, you're sent to a mysterious room. There are two cats guarding two doors, one leading to heaven of AC problems and the other leading to hell NO. One cat likes all divisors of an integ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10187C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "After your death, you're sent to a mysterious room. There are two cats guarding two doors, one leading to heaven of AC problems and the other leading to hell NO. One cat likes all divisors of an integ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ G = (V, E) $ be an undirected multigraph where:  \n- $ V = \\{1, 2, \\dots, N\\} $ is the set of islands.  \n- $ E = E_{\\text{exist}} \\cup E_{\\text{add}} $, with $ |E_{\\text{exist}}...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments