gcd.

Luogu

IDLGP8443

Time1000ms

Memory128MB

DifficultyP1

洛谷原创洛谷月赛

$T$ 组数据，每一组数据给定 $l,r,x$，试求：$\gcd(\lfloor \frac{l}{x}\rfloor,\lfloor \frac{l+1}{x}\rfloor,\cdots,\lfloor \frac{r}{x}\rfloor)$ 的值。 - 其中 $\gcd$ 表示求最大公约数，例如 $\gcd(6,9)=3$，$\gcd(2,4,8)=2$，$\gcd(5,6,7)=1$。特别地，我们定义一个正整数的最大公约数是它自身。 - $\lfloor x \rfloor$ 表示 $x$ 向下取整，例如 $\lfloor 3.14 \rfloor=3$。 ## Input 第一行输入一个正整数 $T$，表示数据组数。对于每一组数据，输入一行三个正整数 $l,r,x$，以空格隔开。 ## Output 对于每一组数据，输出一行，一个正整数表示答案。 [samples] ## Background 与你借星火，容我题山河。 ## Note **【样例解释和说明】** 样例中的 $T=4$，说明有 $4$ 组数据。 - 对于第一组数据，$l=3,r=6,x=1$，即求 $\gcd(\lfloor \frac{3}{1}\rfloor,\lfloor \frac{4}{1} \rfloor, \lfloor \frac{5}{1}\rfloor,\lfloor \frac{6}{1}\rfloor)=1$。 - 对于第二组数据，$l=8,r=11,x=4$，即求 $\gcd(\lfloor \frac{8}{4} \rfloor,\lfloor \frac{9}{4} \rfloor,\lfloor \frac{10}{4}\rfloor,\lfloor \frac{11}{4}\rfloor)=\gcd(2,2,2,2)=2$。 - 对于第三组数据，$l=4,r=4,x=3$，即求 $\gcd(\lfloor \frac{4}{3}\rfloor)=1$。 - 对于第四组数据，类似可得结果是 $1$。 **【数据范围】** - 对于 $10\%$ 的数据，$x=1$。 - 另有 $10\%$ 的数据，$l=r$。 - 另有 $20\%$ 的数据，$r-l \leq 10^5$。 - 对于上述的前 $40\%$ 的数据，$1 \leq x \leq l \leq r \leq 10^9$。 - 对于所有数据，$1 \leq x \leq l \leq r \leq 10^{18}$，$1 \leq T \leq 10$。

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "gcd.",
    "description": {
      "content": "$T$ 组数据，每一组数据给定 $l,r,x$，试求：$\\gcd(\\lfloor \\frac{l}{x}\\rfloor,\\lfloor \\frac{l+1}{x}\\rfloor,\\cdots,\\lfloor \\frac{r}{x}\\rfloor)$ 的值。 - 其中 $\\gcd$ 表示求最大公约数，例如 $\\gcd(6,9)=3$，$\\gcd(2,4,8)=2$，$\\gcd(5,6,7)=1$。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P1"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8443"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "$T$ 组数据，每一组数据给定 $l,r,x$，试求：$\\gcd(\\lfloor \\frac{l}{x}\\rfloor,\\lfloor \\frac{l+1}{x}\\rfloor,\\cdots,\\lfloor \\frac{r}{x}\\rfloor)$ 的值。\n\n- 其中 $\\gcd$ 表示求最大公约数，例如 $\\gcd(6,9)=3$，$\\gcd(2,4,8)=2$，$\\gcd(5,6,7)=1$。...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments