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 数论

上一篇:UVa 11806 Cheerleaders / 容斥原理


下一篇:VLINK 的更新版本