#PQJ36x2306. QOJ 36_2306
QOJ 36_2306
3 迷宫 3.1 题目描述 九条可怜是一个贪玩的女孩子。 暑假快要到了,可怜打算在她家的私人海滩旁边建一座城堡,这样就可以在放暑假的时候 邀请她的朋友们来玩了。同时,可怜打算在城堡的地下修建一座迷宫,因为探险总是一件充满 乐趣的事情。 经过简单的设计,可怜打算修建一座这样的迷宫: • 迷宫可以被抽象成n 个点,nm 条边的有向图。1 号点是唯一的入口也是唯一的出口。 • 每一个点恰好有m 条出边,且这些出边被依次标号为[0, m) 的正整数。 • 迷宫允许自环和重边。 同时,一座优秀的迷宫应该有一定的解谜因素。因此可怜希望每一条从1 号点出发并回到 1 号点的回路都有着一定的规律。 可怜发现,如果把一条从1 出发的路径经过的所有边的编号都记录下来,那么能得到一个 (可能有前导0)的m 进制数;同时对于每一个(可能有前导0)的m 进制数,都能对应回一 条从1 出发的路径。 于是可怜选定了一个整数K,她希望这个迷宫满足一条从1 出发的路径能回到1 当且仅当 这条路径对应的数是K 的倍数。 现在可怜已经选定了m 和K,但是她发现并不是对所有的n,都存在满足上述所有条件的 迷宫设计方案。建造迷宫是一件费时费力的事情,于是可怜想要找到一个最小的满足条件的n。 然而可怜对复杂的计算并不感兴趣,因此她想让你来帮她计算一下这个数值。 3.2 输入Ḑᓣ 第一行输入一个整数T 表示数据组数。 接下来T 行每行两个十进制正整数m, K 表示可怜选定的整数。 3.3 输出Ḑᓣ 对于每组数据,输出一行一个整数表示能够满足所有条件的最小的n。如果不存在这样的 n,输出−1。 3.4 样例输入 3 2 3 6
2 4 6 8 3.5 样例输出 3 3 5 3.6 样例解䞞 第一组数据(左)和第二组数据(右)的一种设计方案如下图所示。其中紫色边表示0 号 边,蓝色边表示1 号边。 3.7 数据㣗ೈ与约定 测试点 m K t 其他约定 1 ≤6 ≤10 ≤100 无 2 ≤100 ≤100 3 4 ≤105 ≤105 5 6 ≤109 ≤109 ≤1000 m 为质数 7 无 8 9 ≤1018 ≤1018 ≤3 × 105 10 对于100% 的数据,保证m ≥2。 7