算法竞赛中无BigInteger库的大整数处理

本文关键字：整数 处理 BigInteger 竞赛 算法 | 更新日期: 2023-09-27 18:18:32

问题:Topcoder SRM 170 500

考虑一个序列{x0, x1, x2，…}。用前一项定义某项xn的关系称为递归关系。线性递归关系是这样的递归关系:xn = c(k-1) * x(n-1) + c(k-2) * x(n-2) +…+ c(0) * x(n-k)其中所有c(i)为实值常数，k为递归关系的长度，n为大于等于k的任意正整数。你将得到一个int[]系数，依次表示，c(0)， c(1)，…c (k - 1)。你也会得到一个int[]初始值，给出x(0)， x(1)，…， x(k-1)和一个int N.你的方法应该返回xN模10。

更具体地说，如果系数的大小为k，则递归关系为Xn =系数[k -1] * Xn -1 +系数[k -2] * Xn -2 +…+系数[0]* xn-k.

例如，如果系数= {2,1}，initial = {9,7}， N = 6，则递归关系为xn = xn-1 + 2 * xn-2，得到x0 = 9, x1 = 7。然后x2 = x1 + 2 * x0 = 7 + 2 * 9 = 25，类似地，x3 = 39, x4 = 89, x5 = 167, x6 = 345，因此您的方法将返回(345模10)= 5。

约束:—代码运行时间必须小于等于2秒—内存利用率不能超过64mb

My attempt Solution:

class RecurrenceRelation
{
    public int moduloTen(int[] coefficients, int[] initial, int N)
    {
        double xn = 0; int j = 0;
        int K = coefficients.Length;
        List<double> xs = new List<double>(Array.ConvertAll<int, double>(initial,
        delegate(int i)
        {
            return (double)i;
        })); 
        if (N < K)
            return negativePositiveMod(xs[N]);
        while (xs.Count <= N)
        {
            for (int i = xs.Count - 1; i >= j; i--)
            {
                xn += xs[i] * coefficients[K--];
            }
            K = coefficients.Length;
            xs.Add(xn);
            xn = 0;
            j++;
        }
        return negativePositiveMod(xs[N]);
    }
    public int negativePositiveMod(double b)
    {
        while (b < 0)
        {
            b += 10;
        }
        return (int)(b % 10);
    }
}

我对这个解决方案的问题是双表示的精度，因为我不能使用第三方库或。net中的BigInteger库来实现这个SRM，我需要找到一种没有它们的解决方法。我想我可以用递归，但我不知道怎么做。

下面是一个测试用例，显示我的代码何时工作，何时不工作

{2,1}，{9,7}， 6 -成功返回5{9,8,7,6,5,4,3,2,1,0}，{1,2,3,4,5,6,7,8,9,10}， 654 -由于double类型

的精度导致返回8而不是5失败有谁能帮我解决这个问题吗?我本来打算考虑用数组来存储这些值，但这对我来说有点难，尤其是如何满足乘法的要求，同时又不受问题中时间和空间复杂度的限制。也许我的整个方法都错了?我希望能得到一些指点和指导(不完全充实的答案)。

谢谢

算法竞赛中无BigInteger库的大整数处理

注意，我们只需要返回xn的模10。

我们还需要知道如果a = b + c，我们有a % 10 = (b % 10 + c % 10) %10.

和a = b*c，所以我们还有a % 10 = (b %10 * c % 10) % 10;

对于

xn = c(k-1) * x(n-1) + c(k-2) * x(n-2) + ... + c(0) * x(n-k) 
            = a0 + a1 + .... + an

(与a0 = c(k -1) *x(n-1)， a1 =…)

我们有xn % 10 = (a0 % 10 + a1 % 10 + ...)%10

对于每个ai = ci*xi，所以ai % 10 = (ci % 10 * xi % 10)% 10。

因此，通过进行所有这些数学计算，我们可以避免使用double，并将结果保持在可管理的大小

正如Pham所回答的那样，诀窍是要意识到您只需要返回一个模，从而绕过溢出问题。这是我的快速尝试。我使用队列来放入最后的结果xN，并取出最早的结果。

    static int solve(int[] coefficients, int[] seed, int n)
    {
        int k = coefficients.Count();
        var queue = new Queue<int>(seed.Reverse().Take(k).Reverse());
        for (int i = k; i <= n; i++)
        {
            var xn = coefficients.Zip(queue, (x, y) => x * y % 10).Sum() % 10;
            queue.Enqueue(xn);
            queue.Dequeue();
        }
        return (int) (queue.Last() );
    }

编辑:得到与您期望的相同的结果，但是我不保证这个示例中没有错误。

相关文章：