[算法擂台]求N个数字的"近似"最大公约数.

Question

最大公约数大家都知道吧. 我就不说了.不知道的话... 我先汗一个,你家小学数学老师被你气死了...求法大家都知道,其实也很简单,(有人大喊,别整三岁的题目,要整整四岁的题目)那...现在来个难度+1的.求近似最大公约数. 啥意思呢?举例说 大家知道 3 是3,6,12,33,这4个数的最大公约数.那啥是近似的呢.. 就是除1和0这2个数字以外,近似值.举例说  7 9 12 最大公约数是1,除0和1以外近似的就是3  假设 7-1=6, 6 9 12 求最大公约数为3 差距为1
7 12 16 最大公约数仍然是1,除0和1以外的近似的就是 4 , 假设 7+1=8, 8 12 16 求最大公约数为4,差距为1
9 12 16 假设最大近似为3 则 差距为1 但是 近似为4 差距也为1 所以取4为近似最大公约数.编程的话,语言不限.关键看思路,怎么去求更合理,效率更高.

Answer 1

假设为long类型. 补充建议:最好不要使用除法和求模运算,这个很慢大家都知道的.

Answer 2

好吧，如果有n个数，那么我觉得最差O(n^3)应该可以搞定，懒得想优化～

Answer 3

说错了是O(n^4)简单描述算法就是前面两个数a1, a2分别枚举区间 [a-n,a+n]，然后作GCD([a1-n,a1+n],[a2-n,a2+n]),假设每个GCD耗时O(1)，则那个GCD两个离散区间耗时O(n^2)，产生最多O(n^2)个数，然后后面呵
～an n-2个数做一次一维的DP，总共耗时O(n^4)～

Answer 4

果然大半夜脑子不好使了，这个算法复杂度是错的，现在只能得到O(n^2)*最大约数个数～算法几乎是死搜了，要DP也行～＝＝＝，＝＝＝＝哭死～

Answer 5

我感觉lz的意思是，每个数都可以+1,-1,或保持不变，总数没有限制，n个数，求近似最大公约数，这样的话，结果最小也是3了。可能咱们对题目的理解不同，你可能认为是总共有n次机会。

Answer 6

简单写了一个，不知道lz是不是这个意思using System;
using System.Collections.Generic;
using System.Linq;namespace ConsoleApplication7
{
    class Program
    {
        static void Main(string[] args)
        {
            long[] items = new long[] {9,12,16};
            Console.WriteLine(SGcd(items));
            Console.ReadKey();
        }        static long SGcd(long[] items)
        {
            HashSet<long> current = new HashSet<long>();
            HashSet<long> backup = new HashSet<long>();
            current.Add(items[0] - 1);
            current.Add(items[0]);
            current.Add(items[0] + 1);            for (int i = 1; i < items.Length; i++)
            {
                for (int j = -1; j <= 1; j++)
                {
                    foreach (var item in current)
                    {
                        long gcd = Gcd(item, items[i] + j);
                        if (gcd > 3)
                            backup.Add(gcd);
                    }
                }                current.Clear();                if (backup.Count == 0)
                    break;                HashSet<long> temp = backup;
                backup = current;
                current = temp;
            }            if (current.Count == 0)
                return 3;
            else
                return current.Max();
        }        static long Gcd(long i, long j)
        {
            while (j != 0) { long r = j; j = i % j; i = r; }
            return i;
        }
    }
}