FPC的一道ACM题
针对某个给出的数字N，找出最小的一个数b。
满足2^b mod N=1
输入样例：
2
5
输出样例：
2^? mod 2 = 1--------------------找不到相应的数
2^4 mod 5 = 1--------------------找到的最小的数为4
问题：怎样找最小的数？要一个个试会超时的！
参考答案:本题目不难啊?? 刚试做了下.....
测试通过了,时间 00:00.01 .(没办法我不会那个PASICAL)
代码如下:
#include "stdio.h"
int main()
{
unsigned int n,k,t;
while(scanf("%d",&n)==1)
{
if(n==1 || n%2==0 ) { printf("2^? mod %d = 1\n",n); continue;}
t=1; k=0;
while(1)
{
if(t==2) break;
if(t%2==0 ) { t/=2; k++; continue;}
t=(n+t)/2;
k++;
}
printf("2^%d mod %d = 1\n",k+1,n);
}
return 0;
}
思路:
解决它用到的只有一个数学知识:
设两整数 m1 = k1 * n + r1;
********* m2 = k2 * n + r2;
***则有: (m1 * m2) mod n = ( k1 * n + r1 ) * ( k2 * n + r2 ) mod n
******** =(r1 * r2) mod n
由于本人表达能力实在有限:我只能举例子加以解释如何利用上式解答问题:
比如说:
输入的是 5
假设存在一个整数 b 使得 2^b mod 5 = 1 ;
由于2 mod 5 =2,那么 利用上公式逆定理可知道,有 2^(b-1) mod 5 = 3,
既 相当与上公式中 m1 = 2; m2 = 2^(b-1)
--->(2 * ? ) mod 5 = 1( ? < 5 ) 显然只能有3.
再往下推:就有 2^(b-2) mod 5 = 4 到这儿,你就可以发现 2^2 = 4 ,
即b-2 = 2, 所以就有 b=4;
不过你再看看
13
这个数据:
同上假设：2^ b mod 13 = 1 => 2^(b-1) mod 13 = 7 =>
********** 2^(b-2) mod 13 = 10 => 2^(b-3) mod 13 = 5 =>
********** 2^(b-4) mod 13 = 9 => 2^(b-5) mod 13 = 11 =>
********** 2^(b-6) mod 13 = 12 => 2^(b-7) mod 13 = 6 =>
********** 2^(b-8) mod 13 = 3 => 2^(b-9) mod 13 = 8 =>
********** 2^(b-9) mod 13 = 4 => 2^(b-11) mod 13 = 2 =>
********** 所以就有 b - 11 = 1 即 b = 12;
从这你是否发现每次往下找的规律呢?
假设 2^(b - i）mod n = r1
如果 r1 为偶数那么 2^(b - i - 1 ）mod n = r1/2 ;
否则 2^(b - i - 1 ）mod n = (n + r1)/2;
你可以试想想,为什么这么推,可以正好满足"最小"条件.
到了这儿,我们就可以很容易推得一个结论:
输入数据 N ;
如果 N 为偶数 ,其必不存在正整数b,使得其满足:2^b mod N=1
而如果 N 为奇数, 其必存在正整数b,使得其满足:2^b mod N=1
证明:
1: 若N为偶数,显然是成立的.
2: 若N为奇数.(假设N >= 3)
证明这个结论之前,我们先引入这个结论:
若 2^(b - i）mod n = r1 和 2^(b - j）mod n = r2 ,其中
i≠j 且 i > j . 那么 r1 ≠ r2 .
证明: 假设 r1 = r2 ,那么有:
[ 2^(b - i）- 2^(b - j）] mod n
= (r1 -r2 ) mod n
= 0
又由于 i≠j
所以 2^(b - i）- 2^(b - j）≠ 0
又 2^(b - i）- 2^(b - j）必为偶数 , n 为奇数,
显然有:
[ 2^(b - i）- 2^(b - j）] mod n ≠ 0
矛盾,故 r1 ≠ r2 .
现在我们来正式证明下N 为奇数的情况:
证明思想主要是: 若存在 2^b mod N=1 ,只要我们推出存在一个i使得 2^(b-i) mod N = 2 即可.(想想,为什么?)
证明: ((在下证明中,我们要保证 b-i 始终大于 0 ))
1: 2^ b mod N=1 =>
2: 2^(b-1) mod N = r1 ( r1 < N )
** 如果r1 = 2 ,命题得证,否则 =>
3: 2^(b-2) mod N = r2 ( r2 < N )
** 如果r2 = 2 ,命题得证,否则 =>
..: .........................=>
N-2: 2^( b - (N-3) ) mod N = r(N-2) ( r(N-2) < N )
** 如果r(b-2) = 2 命题得证,否则 =>
N-1: 2^( b - (N-2) ) mod N = r(N-1) ( r(N-1) < N )
** 如果 r(N-1) = 2 命题得证. 否则:
∵ 1,r1,r2,r3,...,r(N-2),r(N-1) < N (共 N-1个数),且其均不等于2.
又∵他们互相不相等.
又由 "鸟鸽原理"知道: 其中必有一个数等于2.
∴命题得证.
并且我们可以下结论说:
b 存在且 b < N.