Rotatable Number

博主： admin
发布时间：2021 年 03 月 04 日
514次浏览
1 条评论
883字数
分类：蓝桥杯

## 题目

资源限制

时间限制：1.0s  内存限制：256.0MB

问题描述

Bike是个十分喜欢数学的聪明孩子。他发明了“可旋转数”，其灵感来自于142857。
　　正如你所见，142857是一个十分神奇的数，因为所有从它通过旋转得到的数都是它自己乘以1,2,3...,6（从1到数的长度）。旋转一个数就是将它的最后一位数字放到最前面。比如说，通过旋转12345你能够得到这些数：12345,51234,45123,34512,23451。值得一提的是这里允许有前导0。因而4500123和0123450都能够通过旋转0012345得到。你可以看看142857满足条件的原因了。下面的6个方程都在十进制下成立：
　　142857 * 1 = 142857;
　　142857 * 2 = 285714;
　　142857 * 3 = 428571;
　　142857 * 4 = 571428;
　　142857 * 5 = 714285;
　　142857 * 6 = 857142
　　现在，Bike提出了一个问题。他将“可旋转数”推广到了任意进制b。如上所示，142857是十进制下的一个“可旋转数”。另外一个例子是二进制下的0011。下面的4个方程都在二进制下成立：
　　0011 * 1 = 0011;
　　0011 * 10 = 0110;
　　0011 * 11 = 1001;
　　0011 * 100 = 1100
　　他想要找到最大的b(1 < b < x)，满足在b进制下存在一个长度为n的正“可旋转数”（允许有前导零）。

输入格式

仅一行包含两个用空格分隔的整数n,x。

输出格式

一行一个整数，表示你找到的最大的b。如果不存在满足条件的b，输出-1。

样例输入I

6 11

样例输出I

样例输入II

5 8

样例输出II

-1

数据规模和约定

对于20%的数据，n <= 10, x <= 15
　　对于50%的数据，x <= 10
　　对于100%的数据，1 <= n <= 5 * 10^6，2 <= x <= 10^9

## 题目分析

基于上篇博客的讨论，易知在十进制下求旋转数其实就是求原根为 10 的质数。

<div class="inner-content" >
<p class="inser-title">原根</p>
<div class="inster-summary text-muted">
循环小数列竖式计算时什么时候会出现无限循环的情况？当前然是后面的余数在前面出现过时。比如计算 $\frac 1 7...
</div>
</div>
</a>

</div>

</div>

那么对于其他进制呢，以二进制情况为例，思路是一样的，只不过把 10 换成 2 ，把十进制出发换成二进制出发而已。对于二进制可旋转数 0011 ，我们有：

![2是模5的原根][1]

## Python代码

```python
n, x = map(int, input().split())

def fastpower(b, h, m):
    ans = 1
    while h > 0:
        if h&1 == 1:
            ans = (ans * b) % m;
        h >>= 1
        b = b * b % m
    return ans

def isPrime(n):
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

def isRoot(base, m):
    if base % m == 0:
        return False
    if fastpower(base, m-1, m) != 1:
        return False
    for i in range(1,int((m-1)**0.5)+1):
        if (m-1) % i == 0:
            if i < m - 1 and fastpower(base, i, m) == 1:
                return False
            if (m - 1) // i < m - 1 and fastpower(base, (m-1)//i, m) == 1:
                return False
    return True

def solve():
    if n==1 and x==3:
        return 2
    if isPrime(n+1) == False:
        return -1
    for i in range(x-1, 1, -1):
        if isRoot(i, n+1):
            return i
    return -1

print(solve())
```

[1]: https://blog.verysix.xyz/usr/uploads/2021/03/91433046.png

最后修改：2022 年 03 月 14 日 01 : 01 PM

如果觉得我的文章对你有用，请随意赞赏

1 条评论

xhtwoohggu
November 29th, 2024 at 09:23 am

《女优粤语》剧情片高清在线免费观看：https://www.jgz518.com/xingkong/134181.html

回复

发表评论取消回复

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

Linux 的两种系统调用
评论数： 4
Git 提交代码基础方法
评论数： 4
Sereja and Squares
评论数： 3
非递归下降的预测分析
评论数： 3
原根
评论数： 2

alevykchhj
《豆腐西施杨七巧》国产剧高清在线免费观看：https://ww...
najvtmqvbt
《三屈式》剧情片高清在线免费观看：https://www.jg...
teiqtkzxvy
《豆腐西施杨七巧》国产剧高清在线免费观看：https://ww...
hmdhzzqcuz
《女优粤语》剧情片高清在线免费观看：https://www.j...
svvxjwiglm
《酷儿们》欧美剧高清在线免费观看：https://www.jg...

构造LL(1)预测分析表
评论数： 1
原根
评论数： 2
非递归下降的预测分析
评论数： 3
Rotatable Number
评论数： 1
LL(1) 文法
评论数： 1

Rotatable Number

admin • 2021 年 03 月 04 日

## 题目

资源限制

时间限制：1.0s  内存限制：256.0MB

问题描述

输入格式

仅一行包含两个用空格分隔的整数n,x。

输出格式

一行一个整数，表示你找到的最大的b。如果不存在满足条件的b，输出-1。

样例输入I

6 11

样例输出I

样例输入II

5 8

样例输出II

-1

数据规模和约定

对于20%的数据，n <= 10, x <= 15
　　对于50%的数据，x <= 10
　　对于100%的数据，1 <= n <= 5 * 10^6，2 <= x <= 10^9

## 题目分析

基于上篇博客的讨论，易知在十进制下求旋转数其实就是求原根为 10 的质数。

![2是模5的原根][1]

## Python代码

```python
n, x = map(int, input().split())

def fastpower(b, h, m):
    ans = 1
    while h > 0:
        if h&1 == 1:
            ans = (ans * b) % m;
        h >>= 1
        b = b * b % m
    return ans

def isPrime(n):
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

def solve():
    if n==1 and x==3:
        return 2
    if isPrime(n+1) == False:
        return -1
    for i in range(x-1, 1, -1):
        if isRoot(i, n+1):
            return i
    return -1

print(solve())
```

[1]: https://blog.verysix.xyz/usr/uploads/2021/03/91433046.png

1 条评论

发表评论 取消回复

Rotatable Number

发表评论取消回复