ZOJ 1489 2^x mod n = 1 數論

題目大意：

給你正整數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
int main()
{
	int n;
	while(~scanf(%d,&n))
	{
		if( !(n & 1) || n==1)
		{
			printf(2^? mod %d = 1
,n);
			continue;
		}
		int d=1;
		for(int i=1;;i++)
		{
			d*=2;
			if(d%n==1)
			{
				printf(2^%d mod %d = 1
,i,n);
				break;
			}
			d%=n;
		}
	}

	return 0;
}