迷宫
测试数据来自 system/2042
描述
九条可怜是一个贪玩的女孩子。
暑假快要到了,可怜打算在她家的私人海滩旁边建一座城堡,这样就可以在放暑假的时候邀请她的朋友们来玩了。同时,可怜打算在城堡的地下修建一座迷宫,因为探险总是一件充满乐趣的事情。
经过简单的设计,可怜打算修建一座这样的迷宫:
(1). 迷宫可以被抽象成\(n\) 个点,\(nm\) 条边的有向图。\(1\) 号点是唯一的入口也是唯一的出口。
(2). 每一个点恰好有 \(m\) 条出边,且这些出边被依次标号为 \([0,m)\) 的正整数。
(3). 迷宫允许自环和重边。
同时,一座优秀的迷宫应该有一定的解谜因素。因此可怜希望每一条从 \(1\) 号点出发并回到 \(1\) 号点的回路都有着一定的规律。
可怜发现,如果把一条从 \(1\) 出发的路径经过的所有边的编号都记录下来,那么能得到一个(可能有前导 \(0\))的 \(m\) 进制数;同时对于每一个(可能有前导 \(0\))的 \(m\) 进制数,都能对应回一条从 \(1\) 出发的路径。
于是可怜选定了一个整数 \(K\),她希望这个迷宫满足一条从 \(1\) 出发的路径能回到 \(1\) \textbf{当且仅当} 这条路径对应的数是 \(K\) 的倍数。
现在可怜已经选定了 \(m\) 和 \(K\),但是她发现并不是对所有的 \(n\),都存在满足上述所有条件的迷宫设计方案。建造迷宫是一件费时费力的事情,于是可怜想要找到一个最小的满足条件的 \(n\)。
然而可怜对复杂的计算并不感兴趣,因此她想让你来帮她计算一下这个数值。
格式
输入格式
第一行输入一个整数 \(T\) 表示数据组数。
接下来 \(T\) 行每行两个十进制正整数 \(m,K\) 表示可怜选定的整数。
输出格式
对于每组数据,输出一行一个整数表示能够满足所有条件的最小的 \(n\)。如果不存在这样的 \(n\),输出 \(-1\)。
样例1
样例输入1
3
2 3
2 4
6 8
样例输出1
3
3
5
样例解释
第一组数据(左)和第二组数据(右)的一种设计方案如下图所示。其中紫色边表示 \(0\) 号边,蓝色边表示 \(1\) 号边。
限制
对于 \(10\%\) 的数据,\(m\le 6\),\(K\le 10\)。
对于 \(30\%\) 的数据,\(m\le 100\),\(K\le 100\)。
对于 \(50\%\) 的数据,\(m\le 10^5\),\(K\le 10^5\),\(t\le 100\)。
对于 \(80\%\) 的数据,\(m\le 10^9\),\(K\le 10^9\),\(t\le 1000\)。
对于 \(100\%\) 的数据,\(2\le m\le 10^{18}\),\(K\le 10^{18}\),\(t\le 3\times 10^5\)。
来源
ZJOI 2018 Round1
信息
- ID
- 1974
- 难度
- (无)
- 分类
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 上传者