E. Counting Arrays

Codeforces

IDCF893E

Time3000ms

Memory256MB

Difficulty—

combinatoricsdpmathnumber theory

English · Original

Chinese · Translation

Formal · Original

You are given two positive integer numbers _x_ and _y_. An array _F_ is called an __y_\-factorization_ of _x_ iff the following conditions are met: * There are _y_ elements in _F_, and all of them are integer numbers; * . You have to count the number of pairwise distinct arrays that are _y_\-factorizations of _x_. Two arrays _A_ and _B_ are considered different iff there exists at least one index _i_ (1 ≤ _i_ ≤ _y_) such that _A__i_ ≠ _B__i_. Since the answer can be very large, print it modulo 109 + 7. ## Input The first line contains one integer _q_ (1 ≤ _q_ ≤ 105) — the number of testcases to solve. Then _q_ lines follow, each containing two integers _x__i_ and _y__i_ (1 ≤ _x__i_, _y__i_ ≤ 106). Each of these lines represents a testcase. ## Output Print _q_ integers. _i_\-th integer has to be equal to the number of _y__i_\-factorizations of _x__i_ modulo 109 + 7. [samples] ## Note In the second testcase of the example there are six _y_\-factorizations: * { - 4, - 1}; * { - 2, - 2}; * { - 1, - 4}; * {1, 4}; * {2, 2}; * {4, 1}.

给你两个正整数 $x$ 和 $y$。一个数组 $F$ 被称为 $x$ 的一个 _$y$-因子分解_，当且仅当满足以下条件：你需要计算有多少个互不相同的数组是 $x$ 的 $y$-因子分解。两个数组 $A$ 和 $B$ 被认为不同，当且仅当存在至少一个下标 $i$（$1 ≤ i ≤ y$）使得 $A_i ≠ B_i$。由于答案可能非常大，请对 $10^9 + 7$ 取模输出。第一行包含一个整数 $q$（$1 ≤ q ≤ 10^5$）——表示待解决的测试用例数量。接下来 $q$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 ≤ x_i, y_i ≤ 10^6$）。每行代表一个测试用例。请输出 $q$ 个整数。第 $i$ 个整数应等于 $x_i$ 的 $y_i$-因子分解的数量，对 $10^9 + 7$ 取模。在示例的第二个测试用例中，有六个 $y$-因子分解： ## Input 第一行包含一个整数 $q$（$1 ≤ q ≤ 10^5$）——表示待解决的测试用例数量。接下来 $q$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 ≤ x_i, y_i ≤ 10^6$）。每行代表一个测试用例。 ## Output 请输出 $q$ 个整数。第 $i$ 个整数应等于 $x_i$ 的 $y_i$-因子分解的数量，对 $10^9 + 7$ 取模。 [samples] ## Note 在示例的第二个测试用例中，有六个 $y$-因子分解：$\{-4, -1\}$；$\{-2, -2\}$；$\{-1, -4\}$；$\{1, 4\}$；$\{2, 2\}$；$\{4, 1\}$。

**Definitions** Let $ q \in \mathbb{Z} $ be the number of test cases. For each test case $ i \in \{1, \dots, q\} $, let $ x_i, y_i \in \mathbb{Z}^+ $ be given integers. A **$ y_i $-factorization** of $ x_i $ is a $ y_i $-tuple $ (a_1, a_2, \dots, a_{y_i}) \in (\mathbb{Z}^+)^{y_i} $ such that: $$ \prod_{j=1}^{y_i} a_j = x_i $$ Two $ y_i $-factorizations are **distinct** if they differ in at least one component. **Constraints** 1. $ 1 \le q \le 10^5 $ 2. For each test case $ i $: $ 1 \le x_i, y_i \le 10^6 $ **Objective** For each test case $ i $, compute the number of distinct $ y_i $-factorizations of $ x_i $, modulo $ 10^9 + 7 $: $$ \left| \left\{ (a_1, \dots, a_{y_i}) \in (\mathbb{Z}^+)^{y_i} \ \middle|\ \prod_{j=1}^{y_i} a_j = x_i \right\} \right| \mod (10^9 + 7) $$

Samples

Input #1

2
6 3
4 2

Output #1

36
6

API Response (JSON)

{
  "problem": {
    "name": "E. Counting Arrays",
    "description": {
      "content": "You are given two positive integer numbers _x_ and _y_. An array _F_ is called an __y_\\-factorization_ of _x_ iff the following conditions are met: *   There are _y_ elements in _F_, and all of them ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF893E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given two positive integer numbers _x_ and _y_. An array _F_ is called an __y_\\-factorization_ of _x_ iff the following conditions are met:\n\n*   There are _y_ elements in _F_, and all of them ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给你两个正整数 $x$ 和 $y$。一个数组 $F$ 被称为 $x$ 的一个 _$y$-因子分解_，当且仅当满足以下条件：\n\n你需要计算有多少个互不相同的数组是 $x$ 的 $y$-因子分解。两个数组 $A$ 和 $B$ 被认为不同，当且仅当存在至少一个下标 $i$（$1 ≤ i ≤ y$）使得 $A_i ≠ B_i$。由于答案可能非常大，请对 $10^9 + 7$ 取模输出。\n\n第一行包含一个整...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ q \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ i \\in \\{1, \\dots, q\\} $, let $ x_i, y_i \\in \\mathbb{Z}^+ $ be given integers.  \n\nA **$ y_i $-factorizatio...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments