【HDU】 1395 2^x mod n = 1

本文主要是介绍【HDU】 1395 2^x mod n = 1，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2^x mod n = 1

---

题目链接

• 2^x mod n = 1

---

题目大意

    找到一个最小的x满足$2^x\ mod\ n\ =\ 1$如果没有则输出$2^?\ mod\ n\ =\ 1$

---

题解

    我们可以把式子化为$(2*2^{x-1})\ mod\ n\ =\ 1$ 首先可以看到$2^x$是个偶数，要想让该式成立肯定n不能为偶数或者是1，有了这个结论后我们就可以把式子化为$(2*(2^{x-1}\ mod\ n))mod\ n\ =\ 1$于是我们设$F(x-1)\ =\ 2^{x-1}mod\ n\ $所以我们现在有

$$F(x)=(2*F(x-1))mod\ n$$
一直推直到F(x)为1就行了。

---

代码

#include <iostream>
#include <cstring>
#include <cstdio>using namespace std;int n;int main()
{while(scanf("%d",&n)!=EOF){if (n%2==0 || n==1){printf("2^? mod %d = 1\n",n);continue ;}else{int ans=1,cnt=0;while (ans!=1 || cnt==0){cnt++;ans=(ans*2)%n;}printf("2^%d mod %d = 1\n",cnt,n);}}return 0;
}

这篇关于【HDU】 1395 2^x mod n = 1的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---