{"problem":{"name":"接连不断！","description":{"content":"青蛙有 $m+1$ 个无向图，编号为 $0\\sim m$。每个图的点集都是 $V$，点集 $V$ 包含 $n$ 个点，编号为 $0\\sim n-1$。起初所有的图都没有边存在。 接下来，在编号为 $x$ 的图中，对于所有在 $[0, n - 1]$ 中的编号 $i$，青蛙会将编号为 $i$ 的点与编号为 $(i\\cdot x)\\bmod n$ 的点连一条无向边。 他想知道这 $m+1$ 个图中","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10394"},"statements":[{"statement_type":"Markdown","content":"青蛙有 $m+1$ 个无向图，编号为 $0\\sim m$。每个图的点集都是 $V$，点集 $V$ 包含 $n$ 个点，编号为 $0\\sim n-1$。起初所有的图都没有边存在。\n\n接下来，在编号为 $x$ 的图中，对于所有在 $[0, n - 1]$ 中的编号 $i$，青蛙会将编号为 $i$ 的点与编号为 $(i\\cdot x)\\bmod n$ 的点连一条无向边。\n\n他想知道这 $m+1$ 个图中有多少个图是**连通的**，这个问题交给你来回答。\n\n注：\n1. $\\bmod$ 表示取模，$a\\bmod b$ 表示 $a$ 除以 $b$ 得到的余数。\n2. 在一张图中，若在点集内任意两个不同的点 $x, y$ 之间存在至少一条路径，则我们称这个图是**连通的**。\n\n## Input\n\n**本题有多组数据**。\n\n第一行一个整数 $T$，表示数据组数。\n\n接下来 $T$ 行，每行两个整数 $n,m$，含义同上。\n\n## Output\n\n共 $T$ 行，每行一个整数表示答案。\n\n[samples]\n\n## Background\n\n小青蛙被关进了监狱的小黑屋里，他遭受了接连不断的折磨，无论是肉体上还是精神上。\n\n他的精神萎靡不振，他的身体行动迟缓。\n\n有些东西被暂时的压制了，但这些东西越是被压制，它反弹时威力就越大。\n\n他需要一个契机。\n\n## Note\n\n**【样例 #1 解释】**\n\n询问 1：\n\n| 图的编号 | 边集 | 图是否连通 |\n| :------: | :-----------------: | :--------: |\n|   $0$    | $(0,0),(1,0),(2,0)$ |     是     |\n|   $1$    | $(0,0),(1,1),(2,2)$ |     否     |\n|   $2$    | $(0,0),(1,2),(2,1)$ |     否     |\n\n询问 2：\n\n| 图的编号 |    边集    | 图是否连通 |\n| :------: | :-----------------------: | :--------: |\n|   $0$    | $(0,0),(1,0),(2,0),(3,0)$ |     是     |\n|   $1$    | $(0,0),(1,1),(2,2),(3,3)$ |     否     |\n|   $2$    | $(0,0),(1,2),(2,0),(3,2)$ |     是     |\n|   $3$    | $(0,0),(1,3),(2,2),(3,1)$ |     否     |\n|   $4$    | $(0,0),(1,0),(2,0),(3,0)$ |     是     |\n\n询问 3：\n\n| 图的编号 |   边集    | 图是否连通 |\n| :------: | :-----------------------: | :--------: |\n|   $0$    | $(0,0),(1,0),(2,0),(3,0),(4,0)$ |     是     |\n|   $1$    | $(0,0),(1,1),(2,2),(3,3),(4,4)$ |     否     |\n|   $2$    | $(0,0),(1,2),(2,4),(3,1),(4,3)$ |     否     |\n|   $3$    | $(0,0),(1,3),(2,1),(3,4),(4,2)$ |     否     |\n|   $4$    | $(0,0),(1,4),(2,3),(3,2),(4,1)$ |     否     |\n|   $5$    | $(0,0),(1,0),(2,0),(3,0),(4,0)$ |     是     |\n\n所以答案分别为 $1, 3, 2$。\n\n---\n\n**【数据规模与约定】**\n\n**本题开启捆绑测试。**\n\n| $\\text{Subtask}$ | 数据范围 | 分数 |\n| :---: | :---: | :---: |\n| $1$ | $n,m\\le 200$ | $15$ |\n| $2$ | $n,m\\le 3000$ | $30$ |\n| $3$ | $n,m\\le 10^7$ | $15$ |\n| $4$ | $n\\le 3000,m \\le10^{14}$ | $15$ |\n| $5$ | $n,m\\le 10^{14}$ | $25$ |\n\n- 对于 $100\\%$ 的数据，保证 $1\\le T\\le 5,1\\le n,m\\le 10^{14}$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10394","tags":["2024","洛谷原创","O2优化","洛谷月赛"],"sample_group":[["3\n3 2\n4 4\n5 5","1\n3\n2\n"],["5\n4 3\n4 4\n4 5\n4 6\n4 7","2\n3\n3\n4\n4\n"],["3\n1145 1499\n12344 123456\n114514 1919810","2\n41\n17"]],"created_at":"2026-03-03 11:09:25"}}