D. Unusual Sequences

Codeforces

IDCF900D

Time1000ms

Memory256MB

Difficulty—

bitmaskscombinatoricsdpmathnumber theory

English · Original

Chinese · Translation

Formal · Original

Count the number of distinct sequences _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_) consisting of positive integers such that _gcd_(_a_1, _a_2, ..., _a__n_) = _x_ and . As this number could be large, print the answer modulo 109 + 7. _gcd_ here means the [greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor). ## Input The only line contains two positive integers _x_ and _y_ (1 ≤ _x_, _y_ ≤ 109). ## Output Print the number of such sequences modulo 109 + 7. [samples] ## Note There are three suitable sequences in the first test: (3, 3, 3), (3, 6), (6, 3). There are no suitable sequences in the second test.

计算满足以下条件的正整数序列 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai]) 的不同个数：#cf_span[gcd(a1, a2, ..., an) = x] 且 #cf_span[lcm(a1, a2, ..., an) = y]。由于答案可能很大，请对 #cf_span[10^9 + 7] 取模输出。这里的 #cf_span[gcd] 表示最大公约数，#cf_span[lcm] 表示最小公倍数。输入仅一行，包含两个正整数 #cf_span[x] 和 #cf_span[y] (#cf_span[1 ≤ x, y ≤ 10^9])。请输出满足条件的序列个数对 #cf_span[10^9 + 7] 取模的结果。在第一个测试用例中，有三个符合条件的序列：#cf_span[(3, 3, 3)], #cf_span[(3, 6)], #cf_span[(6, 3)]。在第二个测试用例中，没有符合条件的序列。 ## Input 输入仅一行，包含两个正整数 #cf_span[x] 和 #cf_span[y] (#cf_span[1 ≤ x, y ≤ 10^9])。 ## Output 请输出满足条件的序列个数对 #cf_span[10^9 + 7] 取模的结果。 [samples] ## Note 在第一个测试用例中，有三个符合条件的序列：#cf_span[(3, 3, 3)], #cf_span[(3, 6)], #cf_span[(6, 3)]。在第二个测试用例中，没有符合条件的序列。

**Definitions** Let $ x, y \in \mathbb{Z}^+ $ be given integers. Let $ n \in \mathbb{Z}^+ $ be the length of the sequence (variable). Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of positive integers with $ a_i \in \mathbb{Z}^+ $. **Constraints** 1. $ 1 \le x, y \le 10^9 $ 2. $ \gcd(a_1, a_2, \dots, a_n) = x $ 3. $ \max(a_1, a_2, \dots, a_n) = y $ **Objective** Count the number of finite sequences $ A $ of positive integers satisfying the above constraints, modulo $ 10^9 + 7 $.

Samples

Input #1

3 9

Output #1

Input #2

5 8

Output #2

API Response (JSON)

{
  "problem": {
    "name": "D. Unusual Sequences",
    "description": {
      "content": "Count the number of distinct sequences _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_) consisting of positive integers such that _gcd_(_a_1, _a_2, ..., _a__n_) = _x_ and . As this number could be large, print th",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF900D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Count the number of distinct sequences _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_) consisting of positive integers such that _gcd_(_a_1, _a_2, ..., _a__n_) = _x_ and . As this number could be large, print th...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "计算满足以下条件的正整数序列 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai]) 的不同个数：#cf_span[gcd(a1, a2, ..., an) = x] 且 #cf_span[lcm(a1, a2, ..., an) = y]。由于答案可能很大，请对 #cf_span[10^9 + 7] 取模输出。\n\n这里的 #cf_span[gcd] 表示最大公约...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ x, y \\in \\mathbb{Z}^+ $ be given integers.  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the sequence (variable).  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of positive...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments