给定一个正整数n,要求找到最小的x(x>0)满足2^x mod n = 1。

时间:2021-07-17 19:07:57
输入 输入包含多组测试数据。每行一个正整数,代表n的值。

输出

如果最小的x存在,则输出2^x mod n = 1(注意x和n要用具体的值代替),否则输出2^? mod n = 1。

第一种
#include <stdio.h>

int main() {
int n,x,y,;


while(scanf("%d",&n)!=EOF) {
if(n<=1||n%2==0) {
printf("2^? mod %d = 1\n",n);
continue;
}

int w=2,x=1;
while(w!=1) {
x++;
w+=w;
w%=n;
}

printf("2^%d mod %d = 1\n",x,n);

}
return 0;
}

第二种
#include <stdio.h>
#include <stdlib.h>

int main(
{
int mod,n,x,y;
while(scanf("%d",&n)!=EOF) {
if(n<=1||n%2==0) {
printf("2^? mod %d = 1\n",n);
continue;
}
for(x=1,mod=2;; x++,mod+=mod) {
if(mod>n) mod-=n;
if(mod==1) break;
}
printf("2^%d mod %d = 1\n",x,n);
}
return 0;
}


第三种
#include <stdio.h>
#include <math.h>

int main() {

int n;
int i;
while(scanf("%d", &n) != EOF) {
for(i=1; i<20; i++) {
if(( (int)pow(2, i) % n) == 1)
break;
}

if(i <20)
printf("2^%d mod %d = 1\n",i, n);
else
printf("2^? mod %d = 1\n",n);
}

return 0;
}






2.计数输出5个符合条件的数
#include <stdio.h>

int main() {
int mod,n,x,y,count;
count=0;

while(scanf("%d",&n)!=EOF) {
if(n<=1||n%2==0) {
printf("2^? mod %d = 1\n",n);
continue;
}
for(x=1,mod=2;; x++,mod+=mod) {
if(mod>n) mod-=n;
if(mod==1) {
y=x;
printf("y=%d\n",y);
count++;
}
if(count==5) break;
}
printf("2^%d mod %d = 1\n",x,n);
}
return 0;
}