Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

之后怎么求最小的？frkstyc讲一下

Posted by WZPWZPWZP at 2005-05-13 20:23:49 on Problem 2429
In Reply To:分解lcm/gcd的因数，然后就差不多了 Posted by:frkstyc at 2005-05-13 20:18:25

Followed by:

我没怎么细想后面的……lcm/gcd最大是2^63，分解出来最多就12个数，2^12不是很大吧？所以我想枚举 (0) frkstyc 2005-05-13 20:26:26
- 因式分解吗？只有12个数，我以为最多有63个数？ (0) WZPWZPWZP 2005-05-13 20:30:24
  - 相同的因子要合并的，否则gcd就不是那个数了 (0) frkstyc 2005-05-13 20:31:10
    - 不太理解，举个简单的例子好不？ (0) WZPWZPWZP 2005-05-13 20:39:50
      - 最简单的，lcm=4,gcd=1，lcm/gcd=4就只能分解成4而不是2*2，因为两个2假如平分到两边的话gcd就变成2了 (0) frkstyc 2005-05-13 20:42:33
        哦，懂了，谢谢哈：） (0) WZPWZPWZP 2005-05-13 20:45:40
        就是是两边是互质的, (0) tigerhy1 2005-08-21 17:07:13
  - 这个算错了，是15个 (0) frkstyc 2005-05-13 22:30:06
    - 这样就不能轻易枚举了，谁能说一下比较好的算法？ (0) frkstyc 2005-05-13 22:32:45
      - 枚举还是够快的，不过LouTianCheng怎么做的那么快？ (0) frkstyc 2005-05-13 23:09:10
    - ft，你把我的命题思路全部捅出来了！！kick！kick！kick！！！ (0) achilles 2005-05-14 17:55:37
      - 搞来搞去,还是挂在分解上 (0) ArXoR 2005-05-14 17:56:52
      - 这个问题好像是很著名的吧？N年以前我就在书上看过完全一样的问题了…… (0) frkstyc 2005-05-14 18:00:29
      - 呵呵，抱歉哈，是因为我问frkstyc才说的 (0) WZPWZPWZP 2005-05-14 18:05:36
        我记得当时我看书的时候书上把求最小的过程说得特别玄乎，把我都搞晕了，现在想来也就这个样子 (0) frkstyc 2005-05-14 18:09:01
        我到是没见到这个，想法是从1811过来的。:).bullman果然渊博～～：） (0) achilles 2005-05-14 18:24:29
        ft~~~btw我觉得这个题和1811除非突破64位的限制，否则可挖掘的地方不多了 (0) frkstyc 2005-05-14 18:28:33
        思考这个问题中，但是突破之后几乎所有的运算都要重载才行 (0) achilles 2005-05-14 18:32:42
        关键还不是这个，是因数分解算法可能就要加上ECC或者QS了，这样是超有难度的，平时娱乐群众可以，不可能拿来比赛的 (0) frkstyc 2005-05-14 18:35:28
        还有，就是时间会太长，100bit左右分解大概需要30s才能开（我学过网络安全的）。这样几乎是个能接收的时间上线，不能再大了 (0) achilles 2005-05-14 18:42:03
        我觉得与其这样直接套用现成的算法，不如再去想别的有趣的问题吧 (0) frkstyc 2005-05-14 18:44:41
        SP，：） (0) achilles 2005-05-14 18:45:44
        你试试看能不能吧这个64突破，我觉得突破这个限制会难度大增，主要是大数的除法，取模～～ (0) achilles 2005-05-14 18:35:25
        我基本上也是把1811的程序直接搬过来的，不过去掉了素数表换成runtime sieving了，然后再把之前懒得做的优化又加了一些 (0) frkstyc 2005-05-14 18:31:16

Post your reply here:

Home Page Go Back To top