1

我试图在 SPOJ (http://www.spoj.pl/problems/REC/) 上解决这个问题

F(n) = a*F(n-1) + b我们必须找到F(n) Mod (m) 哪里

0 <= a, b, n <=  10^100
       1 <= M <= 100000
F(0)=1

我正在尝试使用 JAVA 中的 BigInteger 来解决它，但是如果我运行从 0 到 n 的循环，它将获得 TLE。我该如何解决这个问题？谁能给点提示？不要发布解决方案。我想提示如何有效地解决它。

4

2 回答 2

1

请注意，残基 mod (m) 的模式应该在线性递归中具有重复模式，并且根据鸽巢原理，长度 <= m。您只需要计算前 m 个条目，然后找出其中哪些条目将适用于 F(n) 以获得 n 的实际值。

它还有助于解决更简单的问题。让我们选择非常小的值，比如 a=2、b=1、m=5、n=1000。

  • F(0) = 1
  • F(1) = 2*F(0) + 1 = 2*1 + 1 = 3 -> 3 模 5 = 3
  • F(2) = 2*F(1) + 1 = 2*3 + 1 = 7 -> 7 模 5 = 2
  • F(3) = 2*F(2) + 1 = 2*7 + 1 = 15 -> 15 Mod 5 = 0
  • F(4) = 2*F(3) + 1 = 2*15 + 1 = 31 -> 31 Mod 5 = 1
  • F(5) = 2*F(4) + 1 = 2*31 + 1 = 63 -> 63 Mod 5 = 3
  • 等等

请注意，残基是 [1, 3, 2, 0, 1, 3, ...]，它将永远重复。那么从这个例子中，你将如何确定 F(1000) Mod 5 而不会一直循环到第 1000 个条目？

于 2012-06-29T15:27:51.767 回答
0

首先，我会告诉你如何解决一个更简单的问题。假设 b 为零。然后你只需要计算一个n mod M。而不是乘 n-1 次，使用分而治之的技术：

// Requires n >= 0 and M > 0.
int modularPower(int a, int n, int M) {
    if (n == 0)
        return 1;
    int result = modularPower(a, n / 2, M);
    result = (result * result) % M;
    if (n % 2 != 0)
        result = (result * a) % M;
    return result;
}

因此，您可以根据 floor(n/2) 计算 a n ，然后将其平方，如果 n 为奇数，则再次乘以 a 。

要解决您的问题，首先定义函数 f(x) = (ax + b) (mod M)。您需要计算fn (1)，即对初始值1应用 fn 次。因此您可以像上一个问题一样使用分治法。幸运的是，两个线性函数的组合也是线性的。您可以用三个整数（两个常数和模数）来表示一个线性函数。编写一个函数，它接受一个线性函数和一个指数，并返回多次组合的函数。

于 2012-06-29T20:59:01.783 回答