[CoE R4 B/Stoi2041] 龙拳

Luogu

IDLGP8302

Time1000ms

Memory256MB

DifficultyP5

模拟数学数论洛谷原创O2优化枚举洛谷月赛

对于 $n \in \mathbb{Z_{\ge 2}}$，设 $g(n)$ 为 $n$ 的小于 $n$ 的最大约数，如 $g(7) = 1, g(12) = 6$。定义 $f(n) = n + g(n)$。记 $f^{(0)}(n)=n$，且对 $m \in \mathbb{Z_{\ge 0}}$ 有 $f^{(m+1)}(n)=f(f^{(m)}(n))$。多次询问，每次询问给定正整数 $n,k$，求最小的自然数 $m_0$，使得对于任意 $m \ge m_0$，均有 $f^{(m)}(n) \mid f^{(m+k)}(n)$。若不存在这样的 $m_0$，则令 $m_0=-1$。 ## Input 第一行一个正整数 $T$ 表示询问次数。接下来 $T$ 行，每行两个正整数 $n,k$，表示一次询问。 ## Output 对于每组询问输出一个整数表示答案。 [samples] ## Background ![](bilibili:BV1fx411N7bU?page=28) ## Note ### 样例解释当 $n=2,k=3$ 时，$m_0=0$。当 $n=3,k=4$ 时不存在满足条件的 $m_0$。 --- ### 数据规模 **本题采用捆绑测试。** - 子任务 $1$（$1$ 分）：$T=k=1$； - 子任务 $2$（$12$ 分）：$T,n,k \le 10$； - 子任务 $3$（$24$ 分）：$T \le 10,n \le 10^5$； - 子任务 $4$（$36$ 分）：$T \le 10^3$； - 子任务 $5$（$27$ 分）：无特殊限制。对于 $100\%$ 的数据，保证 $1 \le T \le 2 \times 10^6$，$2 \le n \le 3 \times 10^7$，$1 \le k \le 10^9$。

Samples

Input #1

2
2 3
3 4

Output #1

0
-1

API Response (JSON)

{
  "problem": {
    "name": "[CoE R4 B/Stoi2041] 龙拳",
    "description": {
      "content": "对于 $n \\in \\mathbb{Z_{\\ge 2}}$，设 $g(n)$ 为 $n$ 的小于 $n$ 的最大约数，如 $g(7) = 1, g(12) = 6$。 定义 $f(n) = n + g(n)$。记 $f^{(0)}(n)=n$，且对 $m \\in \\mathbb{Z_{\\ge 0}}$ 有 $f^{(m+1)}(n)=f(f^{(m)}(n))$。 多次询问，每次询问给定正整数",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8302"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "对于 $n \\in \\mathbb{Z_{\\ge 2}}$，设 $g(n)$ 为 $n$ 的小于 $n$ 的最大约数，如 $g(7) = 1, g(12) = 6$。\n\n定义 $f(n) = n + g(n)$。记 $f^{(0)}(n)=n$，且对 $m \\in \\mathbb{Z_{\\ge 0}}$ 有 $f^{(m+1)}(n)=f(f^{(m)}(n))$。\n\n多次询问，每次询问给定正整数...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments