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

我没怎么细想后面的……lcm/gcd最大是2^63，分解出来最多就12个数，2^12不是很大吧？所以我想枚举

Posted by frkstyc at 2005-05-13 20:26:26 on Problem 2429
In Reply To:之后怎么求最小的？frkstyc讲一下 Posted by:WZPWZPWZP at 2005-05-13 20:23:49

Followed by:

因式分解吗？只有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