Problem Description
Give a number n, find the minimum x(x>0) that satisfies 2^x mod n = 1.
Input
One positive integer on each line, the value of n.
Output
If the minimum x exists, print a line with 2^x mod n = 1.
Print 2^? mod n = 1 otherwise.
You should replace x and n with specific numbers.
Sample Input
2
5
Sample Output
2^? mod 2 = 1
2^4 mod 5 = 1
题意很简单,就不用说了吧。
这个题主要就是会超范围,在这里,可以用取余的方法解决整数范围问题。
然后暴力就可以了。
首先防范一下n为偶数和等于1的情况。
import java.util.Scanner; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()){ int n = sc.nextInt(); if(n%2==0||n==1){ System.out.println("2^? mod "+n+" = 1"); continue; } int x=1; boolean is = true; for(int i=1;i<5000;i++){ x=x*2; x=x%n; if(x%n==1){ is=false; System.out.println("2^"+i+" mod "+n+" = 1"); break; } } if(is){ System.out.println("2^? mod "+n+" = 1"); } } } }