游客 注册 | 登录
中文 | En

1051 - 2^x mod n = 1

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 32 MB

给你一个正整数n，要求你找到最小的x（x>0）满足2^x mod n = 1。

题目输入

输入包含多组测试数据。每行一个正整数，代表n的值。

题目输出

如果最小的x存在，则输出2^x mod n = 1（注意x和n要用具体的值代替），否则输出2^? mod n = 1。

输入/输出样例

输入格式

2
5

输出格式

2^? mod 2 = 1
2^4 mod 5 = 1

C语言解答

#include<stdio.h>

int main()
{
	int n,x,i,s;
	while(scanf("%d",&n)!=EOF)
	{
		if(n%2==0||n==1)
			printf("2^? mod %d = 1\n",n);
		else
		{
			for(s=i=2;;i++)
			{
				s*=2;
				if(s%n==1)
				{
					printf("2^%d mod %d = 1\n",i,n);
					break;
				}
				s%=n;
			}
		}
	}
	return 0;
}

C++解答

#include<stdio.h>

int main()
{
	int n,x,i,s;
	while(scanf("%d",&n)!=EOF)
	{
		if(n%2==0||n==1)
			printf("2^? mod %d = 1\n",n);
		else
		{
			for(s=i=2;;i++)
			{
				s*=2;
				if(s%n==1)
				{
					printf("2^%d mod %d = 1\n",i,n);
					break;
				}
				s%=n;
			}
		}
	}
	return 0;
}

Java解答

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNextInt()){
            int n = in.nextInt();
            int b = Integer.MAX_VALUE;
            if(n==1||n%2==0){
                System.out.println("2^? mod "+n+" = 1");
                continue;
            }
            else{
                for(int i=1;i<b;i++){
                    if(Math.pow(2,i)%n==1){
                        System.out.println("2^"+i+" mod "+n+" = 1");break;
                    }
                }
            }
        }
    }
}
请先登陆