2 qq 31601743 qq_31601743 于 2016.04.15 19:36 提问

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

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
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
CSDNXIAON   2016.04.15 19:42

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

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!