[蓝桥杯青少年组国赛 2024] 第三题

Luogu

IDLGB4308

Time1000ms

Memory512MB

DifficultyP3

2024素数判断,质数,筛法蓝桥杯青少年组

因数：也称约数。如果整数 $a$ 除以整数 $b$，商为整数且余数为 $0$，则称 $b$ 是 $a$ 的因数。例如：$1$、$2$、$3$、$6$ 都是 $6$ 的因数。素数：也称质数，是指在大于 $1$ 的自然数中，除了 $1$ 和它本身以外没有其他因数的数。例如：$2$、$3$、$5$ 是素数，$4$、$6$、$8$ 不是素数。平方数：指的是可以写成某个整数的平方的数。例如：$4$（$2^2$）、$9$（$3^2$）、$16$（$4^2$）都是平方数。莫比乌斯函数 $\mu(n)$ 定义如下： 1. 若 $n = 1$，则 $\mu(n) = 1$； 2. 若 $n$ 的因数中有大于 $1$ 的平方数，则 $\mu(n) = 0$； 3. 若 $n$ 的因数中没有大于 $1$ 的平方数，且 $n = P_1 \times P_2 \times \cdots \times P_k$（其中 $P_1, P_2, \ldots, P_k$ 为 $k$ 个不同的素数），则 $\mu(n) = (-1)^k$。例如： - $8$ 的因数有 $1$、$2$、$4$、$8$，其中大于 $1$ 的平方数有 $4$，所以 $\mu(8) = 0$； - $15$ 的因数有 $1$、$3$、$5$、$15$，没有大于 $1$ 的平方数，且 $15 = 3 \times 5$，所以 $\mu(15) = (-1)^2 = 1$； - $30$ 的因数有 $1$、$2$、$3$、$5$、$6$、$10$、$15$、$30$，没有大于 $1$ 的平方数，且 $30 = 2 \times 3 \times 5$，所以 $\mu(30) = (-1)^3 = -1$。给定两个正整数 $m$ 和 $n$，请计算 $m$ 到 $n$ 之间（含 $m$ 和 $n$）所有整数的莫比乌斯函数值之和。 ## Input 一行输入两个正整数 $m$ 和 $n$（$1 \leq m \leq n \leq 2 \times 10^7$），整数之间以一个空格隔开。 ## Output 输出一个整数，表示 $m$ 到 $n$ 之间（含 $m$ 和 $n$）所有整数的莫比乌斯函数值之和。 [samples]

Samples

Input #1

1 10

Output #1

-1

API Response (JSON)

{
  "problem": {
    "name": "[蓝桥杯青少年组国赛 2024] 第三题",
    "description": {
      "content": "因数：也称约数。如果整数 $a$ 除以整数 $b$，商为整数且余数为 $0$，则称 $b$ 是 $a$ 的因数。例如：$1$、$2$、$3$、$6$ 都是 $6$ 的因数。 素数：也称质数，是指在大于 $1$ 的自然数中，除了 $1$ 和它本身以外没有其他因数的数。例如：$2$、$3$、$5$ 是素数，$4$、$6$、$8$ 不是素数。 平方数：指的是可以写成某个整数的平方的数。例如：$4$（",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4308"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "因数：也称约数。如果整数 $a$ 除以整数 $b$，商为整数且余数为 $0$，则称 $b$ 是 $a$ 的因数。例如：$1$、$2$、$3$、$6$ 都是 $6$ 的因数。\n\n素数：也称质数，是指在大于 $1$ 的自然数中，除了 $1$ 和它本身以外没有其他因数的数。例如：$2$、$3$、$5$ 是素数，$4$、$6$、$8$ 不是素数。\n\n平方数：指的是可以写成某个整数的平方的数。例如：$4$（...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments