H. 目标是成为数论大师

Codeforces

IDCF10217H

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

小白非常不擅长数论，在强老师的数论课上，小白听着听着又睡着了（毕竟梦里什么都有）。小白梦见自己成为了数论大师，只用了三分钟就熟练地写出了一道拉格朗日反演套多项式逆元和快速数论变换的好题。但是当他醒来一看，他还是对数论的题目一窍不通。现在就有一道简单题摆在小白的面前，聪明的你能帮帮他吗？定义经过函数的一次映射就能回到自身的点为函数的不动点（Fix Point）。换句话说，给定函数 $f (x)$，它的不动点就是所有使得 $f (x) = x$ 成立的 $x$ 的集合。如函数 $f (x) = x$ 有无穷多个不动点，而函数 $f (x) = 2 x -1$ 则只有 $x = 1$ 这一个不动点。请你找出函数 $f (x) = sqrt(a x) + b$ 的所有不动点。第一行输入一个正整数 $T " "(1 <= T <= 100)$，表示数据组数。接下来 $T$ 组数据，每组数据输入两个整数 $a$ 和 $b " "(-10^3 <= a, b <= 10^3)$，描述本组输入的函数 $f (x) = sqrt(a x) + b$，保证该函数至少存在一个不动点，且所有的不动点均为整数。对于每组数据，第一行请输出一个正整数 $k$，表示函数 $f (x) = sqrt(a x) + b$ 的不动点个数。第二行请从小到大依次输出 $k$ 个整数 $x_1, x_2, \\\\cdots, x_k " "(x_1 < x_2 < \\\\cdots < x_k)$ 由空格间隔开，描述函数 $f (x)$ 的不动点集合，注意换行。 ## Input 第一行输入一个正整数 $T " "(1 <= T <= 100)$，表示数据组数。接下来 $T$ 组数据，每组数据输入两个整数 $a$ 和 $b " "(-10^3 <= a, b <= 10^3)$，描述本组输入的函数 $f (x) = sqrt(a x) + b$，保证该函数至少存在一个不动点，且所有的不动点均为整数。 ## Output 对于每组数据，第一行请输出一个正整数 $k$，表示函数 $f (x) = sqrt(a x) + b$ 的不动点个数。第二行请从小到大依次输出 $k$ 个整数 $x_1, x_2, \\\\cdots, x_k " "(x_1 < x_2 < \\\\cdots < x_k)$ 由空格间隔开，描述函数 $f (x)$ 的不动点集合，注意换行。 [samples]

**Definitions** Let $ f(x) = \sqrt{a x} + b $, where $ a, b \in \mathbb{Z} $. A fixed point of $ f $ is a value $ x \in \mathbb{Z} $ such that $ f(x) = x $. **Constraints** 1. $ 1 \le T \le 100 $ 2. For each test case: $ -10^3 \le a, b \le 10^3 $ 3. $ f(x) = x $ has at least one integer solution. 4. All fixed points are integers. 5. $ \sqrt{a x} $ is defined and non-negative (i.e., $ a x \ge 0 $ and $ \sqrt{a x} \in \mathbb{R}_{\ge 0} $). **Objective** For each test case, find all integer solutions $ x $ to the equation: $$ x = \sqrt{a x} + b $$ and output them in increasing order.

API Response (JSON)

{
  "problem": {
    "name": "H. 目标是成为数论大师",
    "description": {
      "content": "小白非常不擅长数论，在强老师的数论课上，小白听着听着又睡着了（毕竟梦里什么都有）。小白梦见自己成为了数论大师，只用了三分钟就熟练地写出了一道拉格朗日反演套多项式逆元和快速数论变换的好题。但是当他醒来一看，他还是对数论的题目一窍不通。现在就有一道简单题摆在小白的面前，聪明的你能帮帮他吗？ 定义经过函数的一次映射就能回到自身的点为函数的不动点（Fix Point）。换句话说，给定函数 $f (x)$",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10217H"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小白非常不擅长数论，在强老师的数论课上，小白听着听着又睡着了（毕竟梦里什么都有）。小白梦见自己成为了数论大师，只用了三分钟就熟练地写出了一道拉格朗日反演套多项式逆元和快速数论变换的好题。但是当他醒来一看，他还是对数论的题目一窍不通。现在就有一道简单题摆在小白的面前，聪明的你能帮帮他吗？\n\n定义经过函数的一次映射就能回到自身的点为函数的不动点（Fix Point）。换句话说，给定函数 $f (x)$...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ f(x) = \\sqrt{a x} + b $, where $ a, b \\in \\mathbb{Z} $.  \nA fixed point of $ f $ is a value $ x \\in \\mathbb{Z} $ such that $ f(x) = x $.\n\n**Constraints**  \n1. $ 1 \\le T \\le 100...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments