[原创]二进制数`-求公约数-？++++

主题：[原创]二进制数`-求公约数-？++++

blackmark [专家分：210] 发布于 2006-09-05 15:35:00

怎样在二进制下求最小公约数？

本帖地址： http://bbs.pfan.cn/post/190566.html

回复列表（共12个回复）

沙发

贺天行宝 [专家分：2300] 发布于 2006-09-05 21:17:00

最小公约数？！最大把？
我没有好办法，先换算成十进制怎么样?

板凳

blackmark [专家分：210] 发布于 2006-09-05 22:16:00

不好意思打错了```
     是的是最大公约数;
   但是数据大小是10^20000;
  用的是二进制表示的``
  谢谢!!~~

3 楼

济公二世 [专家分：200] 发布于 2006-09-05 23:21:00

哎呀 !先把2进制转化成10进制再求就OK了嘛?如果你一定要在2进制上求!我没有什么方法.你自己想吧,我觉得不会很简单

4 楼

李是谁 [专家分：10] 发布于 2006-09-06 17:40:00

[img]http://ngjc.net/upload/forum/200604/20060408001649ss.gif[/img]

5 楼

dorremon1992 [专家分：870] 发布于 2006-09-08 21:32:00

!!!

6 楼

interegg [专家分：80] 发布于 2006-09-09 21:19:00

同意一楼的观点,换成十进制后做吧,若是二进制那要看看有什么规律没?可不可以走捷径???
[em2]

7 楼

blackmark [专家分：210] 发布于 2006-09-12 11:56:00

谢谢大家支持哈```
但是请大家看下数据范围```

8 楼

maxumi [专家分：2200] 发布于 2006-09-12 14:42:00

例如：a=10010110
b=1001

算法如下:

Step1: 判断a与b大小, 把小的那个数末尾补足0, 使其与较大数的位数相同, 得到c. <a=10010110, b=1001, c=10010000>

Step2: 再判断 <a与b中较大的那个数> 与c大小, 然后大减小得到d.(别告诉我你不会高精度减法...) <a=10010110 , b=1001, c=10010000, d=110> ,若d=0, 则最大公约数=<a与b中较小的那个数>, end.

Step3: <a与b中较大的那个数>:=d. <a=110, b=1001>

Step4: 转到Step1.

啊，还有一点，string最长只能有255字节，你可以用ansistring, 那个可以长到2147483647字节，当然，前提是你用FreePascal, 而不是TurboPascal.

不好意思, 本人懒得写程序, 只写了个算法, 凑合着看吧XD

如果AC了, 别忘了给我30分~~

9 楼

blackmark [专家分：210] 发布于 2006-11-22 20:29:00

只是因大家的关心所以加分```
更是由于大家的爱心```

10 楼

blackmark [专家分：210] 发布于 2006-11-22 20:31:00

补充:
我用的是LAZARUS

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：[原创]二进制数`-求公约数-？++++

回复列表（共12个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：[原创]二进制数`-求公约数-？++++

回复列表 （共12个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共12个回复）