首页 > 代码库 > HDU-1395-2^x mod n = 1(数学题(二次出错))

HDU-1395-2^x mod n = 1(数学题(二次出错))

题目链接:

http://acm.hdu.edu.cn/showproblem.php?pid=1395

这题一定要滴水不漏的把所有代码全部看完。

这个题目是一个数学类型的题,我也没思路,只知道n==1||n%2==0时,x是找不到的,其他则不知道还有没有n存在x是找不到的,

还有一个,暴力搜索时不知道搜到哪里为止,提交,则超时,看了别人的博客:如果a和n互质且a<n则a^x%n=1,因此在此题中,a为2

所以只要a!=1&&a%2!=0,则一定存在x,

#include<stdio.h>
int main(void)
{
int s,n;
while(scanf("%d",&n)==1)
{
if(n%2==0||n==1)
{
printf("2^? mod %d = 1\n",n);
continue;
}
int m=2;
s=1;
int k=0;
for(;;)
{
s=s*m;
k++;
if(s==n+1)
{
printf("2^%d mod %d = 1\n",k,n);
break;
}
if(s>n+1)
s=s%n;//防止数据过大溢出

}

}
return 0;
}

 

 

另一种解法

#include<stdio.h>
int main(void)
{
int s,n,i;
int m;
while(scanf("%d",&n)==1)
{
if(n==1||n%2==0)
{
printf("2^? mod %d = 1\n",n);
continue;
}
s=1;
m=2;
for(i=1;i<=n;i++)
{
s=s*m;
if(s%n==1)
break;
s=s%n;//防止溢出;
}
if(i<=n)
printf("2^%d mod %d = 1\n",i,n);
else
printf("2^? mod %d = 1\n",n);
}
return 0;
}

 

解释

网友问答

为什么是最多执行 n 次呢?不好意思反应不过来^_^

2^k % n 最多只有n种不同结果
之后就会开始循环

所以最多只需要尝试n次,如果有解的话n次以内就有解,n次以内没有解的话再往后面试也不可能有解

 

 

第二种的修改

#include<stdio.h>
int main(void)
{
int s,n,i;
int m;
while(scanf("%d",&n)==1)
{
if(n==1||n%2==0)
{
printf("2^? mod %d = 1\n",n);
continue;
}
s=1;
m=2;
for(i=1;i<=n;i++)
{
s=s*m;
if(s%n==1)
break;
s=s%n;
}
if(i<=n)
printf("2^%d mod %d = 1\n",i,n);
//else
//printf("2^? mod %d = 1\n",n);
}
return 0;
}

 

同样也会过(AC)第一种方法可解释;

 

 

以上全是他人的,别人的毕竟是别人的,只有自己的才会更深刻

WA  Time Limit Exceeded

#include<stdio.h>
#include<math.h>
int main(void)
{
int s,n,i;
int m;
while(scanf("%d",&n)==1)
{
if(n==1||n%2==0)
{
printf("2^? mod %d = 1\n",n);
continue;
}
s=1;
m=2;
for(i=1;i<=n;i++)
{
s=(int)(pow(2,i));
if(s%n==1)
break;
s=s%n;
}
if(i<=n)
printf("2^%d mod %d = 1\n",i,n);
}
return 0;
}

 

为什么会  Time Limit Exceeded,主要是s=(int)(pow(2,i));两个方面(一)强制转换耗时,(二)pow函数耗时,导致Time Limit Exceeded。

HDU-1395-2^x mod n = 1(数学题(二次出错))