UC知道FPC的一道ACM题
来源：百度知道 编辑：UC知道 时间：2024/05/22 06:10:08
针对某个给出的数字N，找出最小的一个数b。
满足2^b mod N=1
输入样例：
2
5
输出样例：
2^? mod 2 = 1--------------------找不到相应的数
2^4 mod 5 = 1--------------------找到的最小的数为4
问题：怎样找最小的数？要一个个试会超时的！
这道题是浙江大学ACM的1489题！我急切需要PASCAL解法！帮帮忙哦！~
满足2^b mod N=1
输入样例：
2
5
输出样例：
2^? mod 2 = 1--------------------找不到相应的数
2^4 mod 5 = 1--------------------找到的最小的数为4
问题：怎样找最小的数？要一个个试会超时的！
这道题是浙江大学ACM的1489题！我急切需要PASCAL解法！帮帮忙哦！~
本题目不难啊?? 刚试做了下.....
测试通过了,时间 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,<