- 有一座(n)个点（标号为(0sim n-1)）的迷宫，每个点各自连出(m)条边（可有重边和自环，标号分别为(0sim m-1)）。
- 从(0)号点出发，把每次选择的边的编号记录下来得到一个(m)进制数。
- 给定(m,k)，求最小的(n)使得能构造出一个合法的迷宫，使得一条路径最终走回(0)号点当且仅当它对应的(m)进制数是(k)的倍数。
- (m,kle10^{18})
(n=k)的构造方案
考虑对于点(x)，令其第(i)条边连向((xcdot m+i)\%k)，这样一来一条路径走到的点的编号，就等于其对应(m)进制数模(k)的余数。
那么一条路径走到(0)号点，等价于对应(m)进制数模(k)余(0)，也就是(k)的倍数，符合题意。
这个构造完美利用了题目给出的条件，在点的编号和路径的(m)进制数间建立起了直接联系，说实话已经算是一步挺妙的转化了。
缩点获取最优方案
两个点能缩在一起，当且仅当这两个点是等价的，也就是说这两个点每条边指向的点必须相同。
容易发现一次缩点之后可能使得一些新的点变得等价，但方便起见我们先讨论第一次缩点。
两个点(x,y)缩点的充要条件是(forall iin[0,m),xm+iequiv ym+i(mod k))，但这个(i)显然没啥意义，两边可以同时减去，因此实际上就是要满足(xmequiv ym(mod k))。
令(g=gcd(m,k))，并设(m'=frac mg,k'=frac kg)。
则原式可以化作(xm'equiv ym'(mod k'))，即(xequiv y(mod k'))。
一个点的编号可以表示为(u imes k'+v)，那么根据我们得出的结论，缩点的充要条件是(v)相等。
不同的(v)总共有(k')个，因此能缩的点数就应该是((k-1)-k')（要减(1)是因为(0)号点作为一个特殊点无法缩去）。
递归缩点
之前就提到了，一次缩点之后，因为一些原本不相同的点变得相同了，所以可能会使得一些新的点变得等价，因此这里的缩点需要递归求解。
此时发现(x,y)能被缩点等价于 (xcdot m^dequiv ycdot m^d(mod k))。我们仍想化出先前(xequiv y(mod k'))这样的等价式子，就发现(k')相当于是(k)进行了(d)次除以与(m)的(gcd)的操作，递归的过程中可以直接记录，并同时用一个变量(t)记录每次(m')的总乘积。
再开一个变量(r)记录剩余的点数，那么这次缩去的点数就应该是(r-k')（因为缩点的时候每种不同的余数都必然有点剩余，可以保证一定存在所有(k')种余数的点）。而这次缩点后就应该有(t)个点无法再被缩，新的(r)就应该是(k'-t)。
综上，递归函数只需要记录三个变量(r,t,k)，分别记录剩余点数、(m')总乘积、(d-1)次约分后的(k)。
递归具体细节：边界
显然如果(g=1)肯定无法缩点。而若(r<k‘)，由于点数小于出边构成集合的种类数，也无法再缩点。
如果某一时刻(t>k')，则下次递归的(r=k'-t<0)肯定不行，因此我们递归前要先比较(k')与(t)的大小。又因为(t)乘上当前的(m')之后可能会爆(long long)，所以我们要在更新(t)之前把(t imes m')开(long double)和(k')比较，这样就没问题了。
代码：(O(nlog^2k))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define LL long long
using namespace std;
LL m,k;I LL gcd(Con LL& x,Con LL& y) {return y?gcd(y,x%y):x;}
I LL Solve(Con LL& r,Reg LL t,Con LL& k)//递归缩点
{
LL g=gcd(m,k),k_=k/g,m_=m/g;if(g==1||r<k_) return 0;//g=1或r<k'则无法缩点
return (1.0L*t*m_<=k_?(t*=m_,Solve(k_-t,t,k_)):0)+r-k_;//t>k'无须递归，此次缩去r-k'个点
}
int main()
{
RI Tt;scanf("%d",&Tt);W(Tt--) scanf("%lld%lld",&m,&k),printf("%lld
",k-Solve(k-1,1,k));return 0;//总点数-缩去点数
}