[NOIP 2012 提高组] 同余方程

Luogu

IDLGP1082

Time1000ms

Memory125MB

DifficultyP4

数学2012NOIP 提高组扩展欧几里德算法

求关于 $ x$ 的同余方程 $ a x \equiv 1 \pmod {b}$ 的最小正整数解。 ## Input 一行，包含两个整数 $a,b$，用一个空格隔开。 ## Output 一个整数 $x_0$，即最小正整数解。输入数据保证一定有解。 [samples] ## Note ### 数据规模与约定 - 对于 $40\%$ 的数据，$2 \le b\le 10^3$； - 对于 $60\%$ 的数据，$2 \le b\le 5\times 10^7$； - 对于 $100\%$ 的数据，$2 \le a, b\le 2\times 10^9$。

Samples

Input #1

3 10

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[NOIP 2012 提高组] 同余方程",
    "description": {
      "content": "求关于 $ x$ 的同余方程 $ a x \\equiv 1 \\pmod {b}$ 的最小正整数解。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 128000
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP1082"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "求关于 $ x$ 的同余方程 $ a x \\equiv 1 \\pmod {b}$ 的最小正整数解。\n\n## Input\n\n一行，包含两个整数 $a,b$，用一个空格隔开。\n\n## Output\n\n一个整数 $x_0$，即最小正整数解。输入数据保证一定有解。\n\n[samples]\n\n## Note\n\n### 数据规模与约定\n\n- 对于 $40\\%$ 的数据，$2 \\le b\\le  10^3$；\n-...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments