E. Bash Plays with Functions

Codeforces

IDCF757E

Time3000ms

Memory256MB

Difficulty—

brute forcecombinatoricsdpnumber theory

English · Original

Chinese · Translation

Formal · Original

Bash got tired on his journey to become the greatest Pokemon master. So he decides to take a break and play with functions. Bash defines a function _f_0(_n_), which denotes the number of ways of factoring _n_ into two factors _p_ and _q_ such that _gcd_(_p_, _q_) = 1. In other words, _f_0(_n_) is the number of ordered pairs of positive integers (_p_, _q_) such that _p_·_q_ = _n_ and _gcd_(_p_, _q_) = 1. But Bash felt that it was too easy to calculate this function. So he defined a series of functions, where _f__r_ + 1 is defined as: Where (_u_, _v_) is any ordered pair of positive integers, they need not to be co-prime. Now Bash wants to know the value of _f__r_(_n_) for different _r_ and _n_. Since the value could be huge, he would like to know the value modulo 109 + 7. Help him! ## Input The first line contains an integer _q_ (1 ≤ _q_ ≤ 106) — the number of values Bash wants to know. Each of the next _q_ lines contain two integers _r_ and _n_ (0 ≤ _r_ ≤ 106, 1 ≤ _n_ ≤ 106), which denote Bash wants to know the value _f__r_(_n_). ## Output Print _q_ integers. For each pair of _r_ and _n_ given, print _f__r_(_n_) modulo 109 + 7 on a separate line. [samples]

Bash 在成为最伟大的宝可梦大师的旅途中感到疲惫，于是决定休息一下，玩一些函数。 Bash 定义了一个函数 #cf_span[f0(n)]，表示将 #cf_span[n] 分解为两个因子 #cf_span[p] 和 #cf_span[q] 的方案数，要求满足 #cf_span[gcd(p, q) = 1]。换句话说，#cf_span[f0(n)] 是满足 #cf_span[p·q = n] 且 #cf_span[gcd(p, q) = 1] 的正整数有序对 #cf_span[(p, q)] 的个数。但 Bash 觉得计算这个函数太简单了，于是他定义了一系列函数，其中 #cf_span[fr + 1] 定义为：其中 #cf_span[(u, v)] 是任意有序正整数对，它们不必互质。现在 Bash 想要知道不同 #cf_span[r] 和 #cf_span[n] 对应的 #cf_span[fr(n)] 的值。由于数值可能很大，他希望知道对 #cf_span[109 + 7] 取模的结果。请帮助他！第一行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 106]) —— Bash 想要知道的值的个数。接下来的 #cf_span[q] 行，每行包含两个整数 #cf_span[r] 和 #cf_span[n] (#cf_span[0 ≤ r ≤ 106], #cf_span[1 ≤ n ≤ 106])，表示 Bash 想要知道 #cf_span[fr(n)] 的值。请输出 #cf_span[q] 个整数。对于每组给定的 #cf_span[r] 和 #cf_span[n]，在单独一行输出 #cf_span[fr(n)] 对 #cf_span[109 + 7] 取模的结果。 ## Input 第一行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 106]) —— Bash 想要知道的值的个数。接下来的 #cf_span[q] 行，每行包含两个整数 #cf_span[r] 和 #cf_span[n] (#cf_span[0 ≤ r ≤ 106], #cf_span[1 ≤ n ≤ 106])，表示 Bash 想要知道 #cf_span[fr(n)] 的值。 ## Output 请输出 #cf_span[q] 个整数。对于每组给定的 #cf_span[r] 和 #cf_span[n]，在单独一行输出 #cf_span[fr(n)] 对 #cf_span[109 + 7] 取模的结果。 [samples]

**Definitions** Let $ f_0(n) $ denote the number of ordered pairs of positive integers $ (p, q) $ such that $ p \cdot q = n $ and $ \gcd(p, q) = 1 $. For $ r \geq 0 $, define $ f_{r+1}(n) = \sum_{\substack{u,v \geq 1 \\ u \cdot v = n}} f_r(u) \cdot f_r(v) $. **Constraints** 1. $ 1 \leq q \leq 10^6 $ 2. For each query: $ 0 \leq r \leq 10^6 $, $ 1 \leq n \leq 10^6 $ **Objective** For each query $ (r, n) $, compute $ f_r(n) \mod (10^9 + 7) $.

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "E. Bash Plays with Functions",
    "description": {
      "content": "Bash got tired on his journey to become the greatest Pokemon master. So he decides to take a break and play with functions. Bash defines a function _f_0(_n_), which denotes the number of ways of fact",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF757E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Bash got tired on his journey to become the greatest Pokemon master. So he decides to take a break and play with functions.\n\nBash defines a function _f_0(_n_), which denotes the number of ways of fact...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Bash 在成为最伟大的宝可梦大师的旅途中感到疲惫，于是决定休息一下，玩一些函数。\n\nBash 定义了一个函数 #cf_span[f0(n)]，表示将 #cf_span[n] 分解为两个因子 #cf_span[p] 和 #cf_span[q] 的方案数，要求满足 #cf_span[gcd(p, q) = 1]。换句话说，#cf_span[f0(n)] 是满足 #cf_span[p·q = n] 且...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ f_0(n) $ denote the number of ordered pairs of positive integers $ (p, q) $ such that $ p \\cdot q = n $ and $ \\gcd(p, q) = 1 $.  \nFor $ r \\geq 0 $, define $ f_{r+1}(n) = \\sum_{...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments