Question

c语言大神帮帮忙！！！！

模运算时限：1000ms 内存限制：10000K 总时限：3000ms
描述：
给你一个正整数n，请你找到最小的x(x>0)使得2^x mod n = 1。
输入：
正整数n的值(0 < n <= 10000)。
输出：
如果最小的x存在，则输出2^x mod n = 1，否则输出2^? mod n = 1。输出中你应该将x和n替换为特定的值。
输入样例：
2
5

输出样例：
2^? mod 2 = 1
2^4 mod 5 = 1

提示：

我的程序是：
#include <stdio.h>#include <stdlib.h>
int fact(int n);
int main()
{
int n,k,x;
scanf("%d",&n);
for(x=1;x<10000;x++){
k=(fact(x))%n;
if(k==1){
printf("2^%d mod %d = 1\n",x,n);
break;
}
}

if(x>=10000){
printf("2^? mod %d = 1\n",n);
}
return 0;
}

int fact(int n)
{
if(n==0){
return 1;
}
else{
return 2*fact(n-1);
}
}

但是在测试点中有一个不正确，我用的最蠢的办法，求好的办法。谢谢
#include <stdio.h>
int main()
{int mod,n,x;scanf("%d",&n);if(n<=1||n%2==0){printf("2^? mod %d = 1\n",n);return 0;}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;}
这是最好的算法，但我看不懂！ 希望解释下

Answer 1

不知道这个程序符不符合你的要求

// 取模运算.cpp : Defines the entry point for the console application.//
#include "stdafx.h"
int main(int argc, char* argv[])
{
int n, x;

scanf("%d", &n);
if (n <= 0)
{
printf("n不是正整数！\n");
return 0;
}

if ((n % 2 == 0) || (n == 1))
{
printf("2^? mod %d = 1\n",n);
return 0;
}

x = (n + 1) / 2;

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

好吧，上面的程序我把 2^x 认为是 2*x 了。
你给出的程序应该是循环部分不太懂吧，其实这个循环的作用就是从 2^1 开始分别对n取模，直到得到 2^x - n = 1为止。比如要求x mod y的值，我们当然可以通过这样的方法：用x - y得到一个值z，那其实我们可以认为x除以y等于1余z，但如果z仍然比y大，这就不是真正意义上的余数。就可以再一步用z减去y得到另一个值m，就又可以认为x除以y等于2余m。若m比y小了，那x mod y的值就是m;若m还是比y大，那就再减去y，直到最后得到一个比y小的值就是x mod y的值。
另外还有一点，就是如果2^x mod n = y，那2^(x + 1) mod n当然就等于y + y。如果 y + y的值比n大，那说明这还不是最后的余数，由于原来y的值就不可能比n大，因此y + y也不可能比2n大。再用(y + y) - n就可以得到真正的余数。
上面的循环就是结合了以上两点，最后得到x的值。

最后再说明一下前面判断x不存在的条件好了。1就不用说了，肯定不满足。我们可以把条件写成2^x =q*n + r，然后如果n是偶数的话那q*n也是偶数，2^x的值也是偶数，那r必然也是偶数，不可能为1。

说得比较乱，你自己再看看吧。