{"problem":{"name":"「LAOI-1」GCD","description":{"content":"一张图有 $n$ 个节点，编号为 $1,2,3,\\dots,n$。其中 $i$ 号节点会向 $j$ 号节点连一条边权为 $|i-j|$ 的无向边，当且仅当 $\\gcd(i,j)=i,\\operatorname{lcm}(i,j)=j$ 时连边。现询问 $q$ 次，每次询问求 $x$ 到 $y$ 的最短路径。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":65536},"difficulty":{"LuoguStyle":"P2"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9484"},"statements":[{"statement_type":"Markdown","content":"一张图有 $n$ 个节点，编号为 $1,2,3,\\dots,n$。其中 $i$ 号节点会向 $j$ 号节点连一条边权为 $|i-j|$ 的无向边，当且仅当 $\\gcd(i,j)=i,\\operatorname{lcm}(i,j)=j$ 时连边。现询问 $q$ 次，每次询问求 $x$ 到 $y$ 的最短路径。\n\n## Input\n\n第一行一个 $T$，表示数据组数。\n\n每组数据的第一行两个正整数 $n,q$，表示节点数和询问次数。\n\n接下来 $q$ 行，每行两个正整数 $x,y$，表示起点和终点。\n\n## Output\n\n对于每组询问，输出一个正整数。相邻两个输出以换行符隔开。\n\n[samples]\n\n## Note\n\n注意时空限制，本题不捆绑。\n\n对于 $40\\%$ 的数据，$T,n,q\\le100$;\n\n对于 $100\\%$ 的数据，$1\\le T\\le10^6$，$1\\le n,q\\le10^6$，$1\\le x,y\\le n$，$1\\le \\sum n,\\sum q\\le10^6$。\n\n**请使用更快的 IO 方式**。\n\nupdata on 2024/8/8：\n\n时限上调到 1000ms。/yun","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9484","tags":["搜索","数学","贪心","数论","洛谷原创","O2优化","最短路","最大公约数 gcd"],"sample_group":[["1\n6 4\n1 4\n3 5\n2 5\n2 4","3\n6\n5\n2"]],"created_at":"2026-03-03 11:09:25"}}