(step7.2.1)hdu 1395(2^x mod n = 1—

题目大意:输入一个整数n，输出使2^x mod n = 1成立的最小值K

解题思路:简单数论

1)n可能不能为偶数。因为偶数可不可能模上偶数以后==1.

2)n肯定不可能为1 。因为任何数模上1 == 0；

3)所以n肯定是除1外的奇数

代码如下:

#include <iostream>

using namespace std;

int main(){

	int n;

	while(scanf("%d",&n)!=EOF){

		if(n == 1 || n % 2 == 0){

			cout<<"2^?"<<" mod "<< n << " = 1"<<endl;

		}else{

			int k = 1 ;int temp = 2;

			while(temp != 1){

				temp = temp*2%n;

				k++;

			}

			cout<<"2^" << k<<" mod " << n<<" = 1"<<endl;

		}

	}

}

巴特西

(step7.2.1)hdu 1395(2^x mod n = 1——简单数论)

最新文章

热门文章