{"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$。特别地，我们定义一个正整数的最大公约数是它自身。\n- $\\lfloor x \\rfloor$ 表示 $x$ 向下取整，例如 $\\lfloor 3.14 \\rfloor=3$。\n\n## Input\n\n第一行输入一个正整数 $T$，表示数据组数。\n\n对于每一组数据，输入一行三个正整数 $l,r,x$，以空格隔开。\n\n## Output\n\n对于每一组数据，输出一行，一个正整数表示答案。\n\n[samples]\n\n## Background\n\n与你借星火，容我题山河。\n\n## Note\n\n**【样例解释和说明】**\n\n样例中的 $T=4$，说明有 $4$ 组数据。\n\n- 对于第一组数据，$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$。\n- 对于第二组数据，$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$。\n- 对于第三组数据，$l=4,r=4,x=3$，即求 $\\gcd(\\lfloor \\frac{4}{3}\\rfloor)=1$。\n- 对于第四组数据，类似可得结果是 $1$。\n\n**【数据范围】**\n\n- 对于 $10\\%$ 的数据，$x=1$。\n- 另有 $10\\%$ 的数据，$l=r$。\n- 另有 $20\\%$ 的数据，$r-l \\leq 10^5$。\n- 对于上述的前 $40\\%$ 的数据，$1 \\leq x \\leq l \\leq r \\leq 10^9$。\n- 对于所有数据，$1 \\leq x \\leq l \\leq r \\leq 10^{18}$，$1 \\leq T \\leq 10$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8443","tags":["洛谷原创","洛谷月赛"],"sample_group":[["4\n3 6 1\n8 11 4\n4 4 3\n7 16 2","1\n2\n1\n1"]],"created_at":"2026-03-03 11:09:25"}}