哪位程序高手帮我改一下程序??

来源:百度知道 编辑:UC知道 时间:2024/05/17 21:11:31
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

#include <cstdlib>
#include <iostream>
#include <math.h>
using namespace std;

int main(int argc, char *argv[])
{ int x,n;
while(scanf("%d",&n)!=EOF)
{ int i,t;
for(i=1;i<n;i++)
{ t=(int)pow(2,i);
if(t%n==1) break;
}
if(t%n==1) printf("2^%d mod %d = 1\n",i,n);
else printf("2^? mod %d = 1\n",n);
}
system("PAUSE");
return EXIT_

是你程序超时了,做这种ACM题算法很高的,你写的这个程序表面看没问题,但他里面有大批的测试数据,用你这个执行起来就太慢了,想想有没有好点的算法

ACM的

运行结果完全正确,Time Limit Exceeded

说明采用的算法的时间复杂度不符合要求,算法不对