{"problem":{"name":"「GMOI R1-T3」Number Pair","description":{"content":"我们定义满足如下条件的数对 $(x,y)$ 叫做奇妙数对： $k \\times \\gcd(x,y)=\\operatorname{lcm}(x,y)$ 并且 $P \\le \\gcd(x,y) \\le Q$（保证 $P \\le Q$）。 有 $T$ 组数据，对于每一组数据，给定 $k,P,Q$ 三个数，求符合条件的数对 $(x,y)$ 的对数。 **答案对 $10^9+7$ 取模。**","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8926"},"statements":[{"statement_type":"Markdown","content":"我们定义满足如下条件的数对 $(x,y)$ 叫做奇妙数对：\n\n$k \\times \\gcd(x,y)=\\operatorname{lcm}(x,y)$ 并且 $P \\le \\gcd(x,y) \\le Q$（保证 $P \\le Q$）。\n\n有 $T$ 组数据，对于每一组数据，给定 $k,P,Q$ 三个数，求符合条件的数对 $(x,y)$ 的对数。\n\n**答案对 $10^9+7$ 取模。**\n\n## Input\n\n**本题有多组数据。**\n\n第一行一个整数 $T$，表示数据数量。\n\n接下来 $T$ 行，每行三个整数 $k,P,Q$。\n\n## Output\n\n对于每一组数据，给出对应答案，每组数据一行。\n\n[samples]\n\n## Note\n\n**注意并不寻常的时间限制。**\n\n对于 $100\\%$ 的数据 $1 \\le k \\le 10^{16}$，$1 \\le T \\le 50$，$1 \\le P \\le Q \\le 2\\times 10^9$。\n\n| 测试点 | $k$ | $T$ | $P$ | $Q$ | 总分 |\n| :----------: | :----------: | :----------: | :-------------: | :----------: | :----------: |\n| $1\\sim 3$ | $k \\le 3$ | $T=1$ | $P=1$ | $Q=1$ | $15$ |\n| $4\\sim 8$ | $k \\le 100$ | $T \\le 8$ | $P \\le 30$ |  $Q \\le 30$ |$15$ |\n| $9\\sim 13$ | $k \\le 10^3$ | $T \\le 50$ | $P \\le 500$ | $Q \\le 500$ | $25$ |\n| $14\\sim 18$ | $k \\le 10^{12}$ | $T \\le 50$ | $P \\le 10^4$ | $Q \\le 10^4$ | $15$ |\n| $19\\sim 22$ | $k \\le 10^{13}$ | $T \\le 50$ | $P \\le 10^6$ | $Q \\le 10^6$ | $12$ |\n| $23\\sim 28$ | $k \\le 10^{16}$ | $T \\le 50$ | $P \\le 2\\times10^9$ | $Q \\le 2\\times10^9$ | $18$ |\n\n**本题保证 $k$ 随机生成，并不存在极限卡人数据，时限已经开到 std 两倍，请各位选手放心。**","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8926","tags":["数学","数论","O2优化","最大公约数 gcd"],"sample_group":[["5\n10 1 3\n30 1 5\n997 24 35\n34 39 99\n210 1000 1001","12\n40\n24\n244\n32"]],"created_at":"2026-03-03 11:09:25"}}