E. The Holmes Children

Codeforces

IDCF776E

Time2000ms

Memory256MB

Difficulty—

mathnumber theory

English · Original

Chinese · Translation

Formal · Original

The Holmes children are fighting over who amongst them is the cleverest. Mycroft asked Sherlock and Eurus to find value of _f_(_n_), where _f_(1) = 1 and for _n_ ≥ 2, _f_(_n_) is the number of distinct ordered positive integer pairs (_x_, _y_) that satisfy _x_ + _y_ = _n_ and _gcd_(_x_, _y_) = 1. The integer _gcd_(_a_, _b_) is the greatest common divisor of _a_ and _b_. Sherlock said that solving this was child's play and asked Mycroft to instead get the value of . Summation is done over all positive integers _d_ that divide _n_. Eurus was quietly observing all this and finally came up with her problem to astonish both Sherlock and Mycroft. She defined a _k_\-composite function _F__k_(_n_) recursively as follows: She wants them to tell the value of _F__k_(_n_) modulo 1000000007. ## Input A single line of input contains two space separated integers _n_ (1 ≤ _n_ ≤ 1012) and _k_ (1 ≤ _k_ ≤ 1012) indicating that Eurus asks Sherlock and Mycroft to find the value of _F__k_(_n_) modulo 1000000007. ## Output Output a single integer — the value of _F__k_(_n_) modulo 1000000007. [samples] ## Note In the first case, there are 6 distinct ordered pairs (1, 6), (2, 5), (3, 4), (4, 3), (5, 2) and (6, 1) satisfying _x_ + _y_ = 7 and _gcd_(_x_, _y_) = 1. Hence, _f_(7) = 6. So, _F_1(7) = _f_(_g_(7)) = _f_(_f_(7) + _f_(1)) = _f_(6 + 1) = _f_(7) = 6.

福尔摩斯家的孩子们正在争论谁最聪明。迈克罗夫特让夏洛克和尤罗斯计算 #cf_span[f(n)] 的值，其中 #cf_span[f(1) = 1]，且对于 #cf_span[n ≥ 2]，#cf_span[f(n)] 表示满足 #cf_span[x + y = n] 且 #cf_span[gcd(x, y) = 1] 的不同有序正整数对 #cf_span[(x, y)] 的数量。整数 #cf_span[gcd(a, b)] 表示 #cf_span[a] 和 #cf_span[b] 的最大公约数。夏洛克说解决这个问题轻而易举，并让迈克罗夫特改为计算。求和范围是所有整除 #cf_span[n] 的正整数 #cf_span[d]。尤罗斯安静地观察着这一切，最终提出了一个令夏洛克和迈克罗夫特震惊的问题。她递归地定义了一个 #cf_span[k]-复合函数 #cf_span[Fk(n)] 如下：她要求他们计算 #cf_span[Fk(n)] 对 #cf_span[1000000007] 取模的值。输入一行包含两个用空格分隔的整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 1012]）和 #cf_span[k]（#cf_span[1 ≤ k ≤ 1012]），表示尤罗斯要求夏洛克和迈克罗夫特计算 #cf_span[Fk(n)] 对 #cf_span[1000000007] 取模的值。输出一个整数 —— #cf_span[Fk(n)] 对 #cf_span[1000000007] 取模的值。在第一组样例中，有 #cf_span[6] 个不同的有序对 #cf_span[(1, 6)]、#cf_span[(2, 5)]、#cf_span[(3, 4)]、#cf_span[(4, 3)]、#cf_span[(5, 2)] 和 #cf_span[(6, 1)] 满足 #cf_span[x + y = 7] 且 #cf_span[gcd(x, y) = 1]。因此，#cf_span[f(7) = 6]。于是，#cf_span[F1(7) = f(g(7)) = f(f(7) + f(1)) = f(6 + 1) = f(7) = 6]。 ## Input 输入一行包含两个用空格分隔的整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 1012]）和 #cf_span[k]（#cf_span[1 ≤ k ≤ 1012]），表示尤罗斯要求夏洛克和迈克罗夫特计算 #cf_span[Fk(n)] 对 #cf_span[1000000007] 取模的值。 ## Output 输出一个整数 —— #cf_span[Fk(n)] 对 #cf_span[1000000007] 取模的值。 [samples] ## Note 在第一组样例中，有 #cf_span[6] 个不同的有序对 #cf_span[(1, 6)]、#cf_span[(2, 5)]、#cf_span[(3, 4)]、#cf_span[(4, 3)]、#cf_span[(5, 2)] 和 #cf_span[(6, 1)] 满足 #cf_span[x + y = 7] 且 #cf_span[gcd(x, y) = 1]。因此，#cf_span[f(7) = 6]。于是，#cf_span[F1(7) = f(g(7)) = f(f(7) + f(1)) = f(6 + 1) = f(7) = 6]。

**Definitions** Let $ f(n) $ be the number of ordered pairs of positive integers $ (x, y) $ such that $ x + y = n $ and $ \gcd(x, y) = 1 $. Let $ g(n) = \sum_{d \mid n} f(d) $. Let $ F_k(n) $ be defined recursively: - $ F_1(n) = g(n) $, - For $ k \geq 2 $, $ F_k(n) = F_{k-1}(g(n)) $. **Constraints** $ 1 \leq n \leq 10^{12} $, $ 1 \leq k \leq 10^{12} $ **Objective** Compute $ F_k(n) \mod 1000000007 $.

Samples

Input #1

7 1

Output #1

Input #2

10 2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "E. The Holmes Children",
    "description": {
      "content": "The Holmes children are fighting over who amongst them is the cleverest. Mycroft asked Sherlock and Eurus to find value of _f_(_n_), where _f_(1) = 1 and for _n_ ≥ 2, _f_(_n_) is the number of distin",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF776E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The Holmes children are fighting over who amongst them is the cleverest.\n\nMycroft asked Sherlock and Eurus to find value of _f_(_n_), where _f_(1) = 1 and for _n_ ≥ 2, _f_(_n_) is the number of distin...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "福尔摩斯家的孩子们正在争论谁最聪明。\n\n迈克罗夫特让夏洛克和尤罗斯计算 #cf_span[f(n)] 的值，其中 #cf_span[f(1) = 1]，且对于 #cf_span[n ≥ 2]，#cf_span[f(n)] 表示满足 #cf_span[x + y = n] 且 #cf_span[gcd(x, y) = 1] 的不同有序正整数对 #cf_span[(x, y)] 的数量。整数 #cf_...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ f(n) $ be the number of ordered pairs of positive integers $ (x, y) $ such that $ x + y = n $ and $ \\gcd(x, y) = 1 $.  \nLet $ g(n) = \\sum_{d \\mid n} f(d) $.  \nLet $ F_k(n) $ be...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments