打卡信奥刷题（3444）用C++实现信奥题 P10394 接连不断！

P10394 接连不断题目背景小青蛙被关进了监狱的小黑屋里他遭受了接连不断的折磨无论是肉体上还是精神上。他的精神萎靡不振他的身体行动迟缓。有些东西被暂时的压制了但这些东西越是被压制它反弹时威力就越大。他需要一个契机。题目描述青蛙有m1m1m1个无向图编号为0∼m0\sim m0∼m。每个图的点集都是VVV点集VVV包含nnn个点编号为0∼n−10\sim n-10∼n−1。起初所有的图都没有边存在。接下来在编号为xxx的图中对于所有在[0,n−1][0, n - 1][0,n−1]中的编号iii青蛙会将编号为iii的点与编号为(i⋅x) mod n(i\cdot x)\bmod n(i⋅x)modn的点连一条无向边。他想知道这m1m1m1个图中有多少个图是连通的这个问题交给你来回答。注mod \bmodmod表示取模a mod ba\bmod bamodb表示aaa除以bbb得到的余数。在一张图中若在点集内任意两个不同的点x,yx, yx,y之间存在至少一条路径则我们称这个图是连通的。输入格式本题有多组数据。第一行一个整数TTT表示数据组数。接下来TTT行每行两个整数n,mn,mn,m含义同上。输出格式共TTT行每行一个整数表示答案。输入输出样例 #1输入 #13 3 2 4 4 5 5输出 #11 3 2输入输出样例 #2输入 #25 4 3 4 4 4 5 4 6 4 7输出 #22 3 3 4 4输入输出样例 #3输入 #33 1145 1499 12344 123456 114514 1919810输出 #32 41 17说明/提示【样例 #1 解释】询问 1图的编号边集图是否连通000(0,0),(1,0),(2,0)(0,0),(1,0),(2,0)(0,0),(1,0),(2,0)是111(0,0),(1,1),(2,2)(0,0),(1,1),(2,2)(0,0),(1,1),(2,2)否222(0,0),(1,2),(2,1)(0,0),(1,2),(2,1)(0,0),(1,2),(2,1)否询问 2图的编号边集图是否连通000(0,0),(1,0),(2,0),(3,0)(0,0),(1,0),(2,0),(3,0)(0,0),(1,0),(2,0),(3,0)是111(0,0),(1,1),(2,2),(3,3)(0,0),(1,1),(2,2),(3,3)(0,0),(1,1),(2,2),(3,3)否222(0,0),(1,2),(2,0),(3,2)(0,0),(1,2),(2,0),(3,2)(0,0),(1,2),(2,0),(3,2)是333(0,0),(1,3),(2,2),(3,1)(0,0),(1,3),(2,2),(3,1)(0,0),(1,3),(2,2),(3,1)否444(0,0),(1,0),(2,0),(3,0)(0,0),(1,0),(2,0),(3,0)(0,0),(1,0),(2,0),(3,0)是询问 3图的编号边集图是否连通000(0,0),(1,0),(2,0),(3,0),(4,0)(0,0),(1,0),(2,0),(3,0),(4,0)(0,0),(1,0),(2,0),(3,0),(4,0)是111(0,0),(1,1),(2,2),(3,3),(4,4)(0,0),(1,1),(2,2),(3,3),(4,4)(0,0),(1,1),(2,2),(3,3),(4,4)否222(0,0),(1,2),(2,4),(3,1),(4,3)(0,0),(1,2),(2,4),(3,1),(4,3)(0,0),(1,2),(2,4),(3,1),(4,3)否333(0,0),(1,3),(2,1),(3,4),(4,2)(0,0),(1,3),(2,1),(3,4),(4,2)(0,0),(1,3),(2,1),(3,4),(4,2)否444(0,0),(1,4),(2,3),(3,2),(4,1)(0,0),(1,4),(2,3),(3,2),(4,1)(0,0),(1,4),(2,3),(3,2),(4,1)否555(0,0),(1,0),(2,0),(3,0),(4,0)(0,0),(1,0),(2,0),(3,0),(4,0)(0,0),(1,0),(2,0),(3,0),(4,0)是所以答案分别为1,3,21, 3, 21,3,2。【数据规模与约定】本题开启捆绑测试。Subtask\text{Subtask}Subtask数据范围分数111n,m≤200n,m\le 200n,m≤200151515222n,m≤3000n,m\le 3000n,m≤3000303030333n,m≤107n,m\le 10^7n,m≤107151515444n≤3000,m≤1014n\le 3000,m \le10^{14}n≤3000,m≤1014151515555n,m≤1014n,m\le 10^{14}n,m≤1014252525对于100%100\%100%的数据保证1≤T≤5,1≤n,m≤10141\le T\le 5,1\le n,m\le 10^{14}1≤T≤5,1≤n,m≤1014。C实现#includeiostreamusingnamespacestd;longlongf(longlongn)// n 所有质因数的乘积{longlongres1;for(inti2;1ll*i*in;i){if(n%i0)res*i;while(n%i0)n/i;}if(n!1)res*n;returnres;}intmain(){cin.tie(nullptr);cout.tie(nullptr);intt;cint;while(t--){longlongn,m;std::cinnm;std::coutm/f(n)1\n;}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容