模运算题

Question

我遇到了一个简单算法的问题。问题如下：

问题描述斐波那契数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1.

当n很大时，Fn也很大，现在我们想知道Fn超过10007的余数是多少。

输入格式

输入包含一个整数n。

输出格式

输出行包含一个整数，表示 Fn 除以 10007 的余数。

示例输入 10 示例输出

55

示例输入 22 示例输出

7704

数据大小和约定 1 <= n <= 1,000,000。

我的解决方案如下：

import java.util.Scanner;

/** * */ public class 主要 {

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    System.out.println(recurrence(n));
    in.close();

}


/**
 *
 * @param n
 * @return
 */
public static int recurrence(int n) {
    int f1 = 1;
    int f2 = 1;
    int temp = f1;
    for (int i = 1; i <= n - 2; i++) {
        temp = (f1 + f2)%10007;
        f1 = f2;
        f2 = temp;
    }
    return temp;
}

}

上面的解是对的。但是我想说下面的解决方案有问题。

public static int recurrence(int n) {
    int f1 = 1;
    int f2 = 1;
    int temp = f1;
    for (int i = 1; i <= n - 2; i++) {
        f1 %= 10007;
        f2 %= 10007;
        temp = f1 + f2;
        f1 = f2;
        f2 = temp;
    }
    return temp;
}

不temp = (f1+f2)%10007和f1 %= 10007; f2 %= 10007; temp = f1 + f2;一样吗？

我的英语很差，希望你们能明白我的意思。谢谢！

Answer 1

重写取模结果有一定的属性。 Wikipedia 展示了其中的一些。与此处相关的是：

(a + b) % n = ((a % n) + (b % n)) % n

所以如果你改变

F_n = F_n-1 + F_n-2

到

F_n = (F_n-1 + F_n-2) % 10007

你得到你想要的，因为 F_n-1 和 F_n-2 已经有了 % 10007应用。

static int fibMod(int n, int mod) {
    if (n < 0 || mod < 2)
        throw new IllegalArgumentException();
    if (n <= 1)
        return n;
    int prev = 1, fib = 1;
    for (int i = 3; i <= n; i++)
        fib = (prev + (prev = fib)) % mod;
    return fib;
}

测试

System.out.println(fibMod(10, 10007));
System.out.println(fibMod(22, 10007));
System.out.println(fibMod(1_000_000, 10007));

输出

55
7704
114

模运算题

modular arithmetic problems

java

algorithm

modular-arithmetic

当n很大时，Fn也很大，现在我们想知道Fn超过10007的余数是多少。

输入包含一个整数n。

输出行包含一个整数，表示 Fn 除以 10007 的余数。

55

7704