hdoj 1395 2^x mod n = 1 【暴力】

本文主要是介绍hdoj 1395 2^x mod n = 1 【暴力】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

策略 ： 观察可知，1 或者是能被2整除的数都不会求余等于1， 只需要判断一下是不是除1之外的奇数，在依次查找2^x（mod（n）） ?= 1就可以了

难点：如果每次都是在原来的基础上×2 再判断 会超时。这时候，要用一下同余定理就可以了

AC by SWS;

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1395

代码：

#include<stdio.h>
int main()
{
int n;
while(scanf("%d", &n) == 1){
if(n ==1||n%2==0){
printf("2^? mod %d = 1\n", n);
continue;
}
else{
int sum = 2, i, dc = 1;
for(i = 1; ; i ++)
if(sum%n != 1){
sum = sum%n*2; //同余定理 sum×2%n == （sum%n） ×（2%n） == （2<n） => sum%n*2 
}
else
break;
printf("2^%d mod %d = 1\n", i, n);
}
}
return 0;
}

 

这篇关于hdoj 1395 2^x mod n = 1 【暴力】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---