qq_31601743 于 2016.04.15 19:36 提问

2^x mod n = 1超时怎么解决呀

2^x mod n = 1
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 15197 Accepted Submission(s): 4695

Problem Description
Give a number n, find the minimum x(x>0) that satisfies 2^x mod n = 1.

Input
One positive integer on each line, the value of n.

Output
If the minimum x exists, print a line with 2^x mod n = 1.

Print 2^? mod n = 1 otherwise.

You should replace x and n with specific numbers.

Sample Input
2
5

Sample Output
2^? mod 2 = 1
2^4 mod 5 = 1

2个回答

qq_31601743   2016.04.15 19:37

#include
using namespace std;

int main()
{
int n;
int x;
int d;

``````while(cin >> n)
{
d= 0;
if(n%2==0||n==1)
cout << "2^? mod 2 = 1" << endl;

else
{
x = 1;
while(1)
{
x=x*2;d++;
if(x%n==1)
{
cout << "2^"<<d<< " mod 2 = 1" << endl;
break;
}

}

}

}
return 0;
``````

}

CSDNXIAON   2016.04.15 19:42

2^x mod n = 1
2^x mod n = 1
2^x mod n = 1
----------------------同志你好，我是CSDN问答机器人小N，奉组织之命为你提供参考答案，编程尚未成功，同志仍需努力！