HDU 1395 - 2^x mod n = 1 (欧拉定理 + 快速幂取模)
题意
找出2^x mod n = 1的最小x
思路
欧拉定理$2^{\phi (n)} \equiv 1 \bmod n$
但这并不一定是最小解。
可以从小到大暴力一遍。
还有一种更快的方法，枚举$\phi (n)$的因子，解就在里面。（可是我不会证）
代码
int GetPhi(int n)
{
int m = (int)sqrt(n + 0.5);
int ans = n;
for (int i = 2; i <= m; i++) if (n%i == 0)
{
ans = ans / i * (i-1);
while (n % i == 0) n /= i;
}
if (n > 1) ans = ans / n * (n-1);
return ans;
}
LL Quick_Mod(LL a, LL m, LL n)
{
LL ans = 1;
while (m)
{
if (m & 1) ans = ans * a % n;
a = a*a % n;
m >>= 1;
}
return ans;
}
int main()
{
int n;
while (~scanf("%d", &n))
{
if ((n&1) && n != 1)
{
int i;
int limit = GetPhi(n);
for (i = 1; i < limit; i++)
if (Quick_Mod(2, i, n) == 1)
{
printf("2^%d mod %d = 1\n", i, n);
break;
}
if (i == limit) printf("2^%d mod %d = 1\n", limit, n);
}
else printf("2^? mod %d = 1\n", n);
}
return 0;
}