ZOJ 1489 2^x mod n = 1 数论

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=489

题目大意：

给你正整数n，求最小的x使得2^x mod n = 1。

思路：

n=1无解。任何正数mod 1都为0吧

n为偶数无解，why? 上式可变形为： 2^x=k*n+1，若n为偶数那么k*n+1为奇数，而2^x必为偶数。

n为奇数一定有解，对于乘法逆元：在a mod n的操作下，a存在乘法逆元当且仅当a与n互质。

#include<cstdio>

int main()

{

	int n;

	while(~scanf("%d",&n))

	{

		if( !(n & 1) || n==1)

		{

			printf("2^? mod %d = 1\n",n);

			continue;

		}

		int d=1;

		for(int i=1;;i++)

		{

			d*=2;

			if(d%n==1)

			{

				printf("2^%d mod %d = 1\n",i,n);

				break;

			}

			d%=n;

		}

	}

	return 0;

}

巴特西

ZOJ 1489 2^x mod n = 1 数论

最新文章

热门文章