| 题目名称 | 1939. [CF 303D]循环数 |
|---|---|
| 输入输出 | rotatablenumber.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cstdio
于2015-04-14加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：3， 提交：5， 通过率：60% | ||||
 mikumikumi |
100 | 0.002 s | 0.29 MiB | C++ |
 cstdio |
100 | 0.003 s | 0.31 MiB | C++ |
 宋逸群 |
100 | 5.061 s | 114.76 MiB | C++ |
|
mikumikumi |
50 | 0.002 s | 0.29 MiB | C++ |
|
宋逸群 |
30 | 3.151 s | 46.03 MiB | C++ |
| 关于 循环数 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
%%%%%%%%cstdio
宋逸群
2016-11-10 20:25
2楼
| ||||
【题目描述】
Bike是一位机智的少年，非常喜欢数学。他受到142857的启发，发明了一种叫做“循环数”的数。
如你所见，142857是一个神奇的数字，因为它的所有循环排列能由它乘以1,2，...，6（1到它的长度）得到。循环排列意味着将该数的一些数位从尾部挪到前面。例如，12345的循环排列包括：12345,51234,45123,34512,23451.值得一提的是，允许出现前导零。因此4500123和0123450都是0012345的循环排列。你可以看到142857满足条件的原因。以下六个等式是在十进制下的。
·142857*1=142857
·142857*2=285714
·142857*3=428571
·142857*4=571428
·142857*5=714285
·142857*6=857142
现在Bike有一个问题。他将“循环数”扩展到任意进制b。如前所述，142857是十进制下的循环数。另一个例子是二进制下的0011.以下四个等式是二进制的：
·0011*1=0011
·0011*10=0110
·0011*11=1001
·0011*100=1100
他想要找出最大的b（1<b<x）使得有一个b进制下长度为n的正循环数（允许前导零）。
注意，当你将循环数乘以1到其长度的任意整数时你都应该得到一个它的循环排列。
【输入格式】
一行两个正整数n,x（1<=n<=5*10^6,2<=x<=10^9）
【输出格式】
一个整数b，即你找到的最大的b。若不存在这样的b，输出-1.
【样例输入输出】
Input
6 11
Output
10
Input
5 8
Output
-1