HDU 1395 2^x mod n = 1（暴力枚举）

HDU 1395 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): 15721    Accepted Submission(s): 4870

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

25

Sample Output

2^? mod 2 = 12^4 mod 5 = 1

Author

MA, Xiao

Source

​​ZOJ Monthly, February 2003 ​​

题解：暴力枚举....

TLE代码：

#include#include#include#include#include#include#include#include#include#includetypedef long long LL;using namespace std;int main(){ int x,n; while(cin>>n) { int k=0; for(int i=1;i<=5000;i++) { if((int)pow(2,(double)i)%n==1){ printf("2^%d mod %d = 1\n",i,n);break; } k++; } if(k==5000) cout<<"2^? mod "<

#include#include#include#include#include#include#include#include#include#includetypedef long long LL;using namespace std;int main(){ int k,m,x,n; while(cin>>n) { k=1; x=2; if(n%2==0||n==1) cout<<"2^? mod "<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。