Java实现蓝桥杯算法训练 Rotatable Number（暴力）

试题算法训练 Rotatable Number

资源限制

时间限制：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

　　10

样例输入II

　　5 8

样例输出II

　　-1

数据规模和约定

　　对于20%的数据，n <= 10, x <= 15

　　对于50%的数据，x <= 10

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



import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		// 转自:	https://blog.csdn.net/a1439775520

		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();

		int x = sc.nextInt();

		sc.close();

		if (n==1&&x==3) {

			System.out.println(2);

			return;

		}

		if (!isPrime(n + 1)) {

			System.out.println(-1);

			return;

		}

		for (int i = x - 1; i >1; i--) {

			if (isRoot(i, n + 1)) {

				System.out.println(i);

				return;

			}

		}

		System.out.println(-1);

	}

	private static boolean isRoot(long a, long p) {

		if (a%p==0) {

			return false;

		}

		for (int i = 1; i * i <= p - 1; i++) {

			if ((p - 1) % i == 0) {

				if (i < p - 1 && ex(a, i, p) == 1) {

					return false;

				}

				if ((p - 1) / i < p - 1 && ex(a, (p - 1) / i, p) == 1) {

					return false;

				}

			}

		}

		return true;

	}

	private static long ex(long a, long n, long p) {

		if (n == 0) {

			return 1 % p;

		}

		long res = 1;

		while (n != 0) {

			if ((n & 1) == 1) {

				res = res * a % p;

			}

			n >>= 1;

			a = a * a % p;

		}

		return res;

	}

	private static boolean isPrime(long n) {

		for (int i = 2; i * i <= n; i++) {

			if (n % i == 0) {

				return false;

			}

		}

		return true;

	}

}

巴特西

Java实现蓝桥杯算法训练 Rotatable Number（暴力）

试题算法训练 Rotatable Number

最新文章

热门文章

巴特西

Java实现 蓝桥杯 算法训练 Rotatable Number（暴力）

试题 算法训练 Rotatable Number

最新文章

热门文章

Java实现蓝桥杯算法训练 Rotatable Number（暴力）

试题算法训练 Rotatable Number