[算法]从 CU 抄过来的数学题一个。

arxor

计算F_n可以变成某个系数矩阵乘幂来做...
分析一下递归方程就行了, 中间运算用模m加法和模m乘法来做
乘幂明显可以在O(log(m))里完成了

DoDo

如果问题是：求第200000000个fib数mod 89999931
而不是：求第200000000个fib数的M次方mod 89999931
那么，下面的代码可以工作，不过时间复杂度是O(k)  

[PHP]
#include <stdio.h>

typedef unsigned long int t_ul;

int main()
{
        /* x % n */
        t_ul x = 0;
        t_ul n = 89999931;

        t_ul a = 1;
        t_ul b = 1;
        t_ul k = 200000000;
        t_ul i = 0;
       
        for (i = 2; i < k; i++) {
                x = a + b;
                if (x > n) x -= n;
                b = a;
                a = x;
        }

        printf("result = %u\n", x);
        return 0;
}

[/PHP]

conwood

echo 4

jhuangjiahua

http://blog.chinaunix.net/articl ... 1549&blogId=484

conwood

没关系，求出这个数之后再求一下 fib(2000...000)^M mod 89999931
复杂度是 k+logk=k (省略 O)

Post by DoDo
如果问题是：求第200000000个fib数mod 89999931
而不是：求第200000000个fib数的M次方mod 89999931
那么，下面的代码可以工作，不过时间复杂度是O(k)  

[PHP]
#include <stdio.h>

typedef unsigned long int t_ul;

int main()
{
        /* x % n */
        t_ul x = 0;
        t_ul n = 89999931;

        t_ul a = 1;
        t_ul b = 1;
        t_ul k = 200000000;
        t_ul i = 0;
       
        for (i = 2; i < k; i++) {
                x = a + b;
                if (x > n) x -= n;
                b = a;
                a = x;
        }

        printf("result = %u\n", x);
        return 0;
}

[/PHP]

DoDo

Post by conwood
没关系，求出这个数之后再求一下 fib(2000...000)^M mod 89999931
复杂度是 k+logk=k (省略 O)

这一点我倒是也想到了，不过要求x^m%n也是件痛苦的事。我先寻找使得x^k%n＝1 的k，再通过x^(m%k)%n来得到结果。但是k最大可能大到n－1，这时如果m足够大，那么这一部分的复杂度是n。不知道logk的算法是如何实现的。

代码如下
[PHP]
#include <stdio.h>

typedef unsigned long int t_ul;

int main()
{
        /* x ^ m % n */
        t_ul x = 0;
//        t_ul m = 100000000;        // 在 m > n 的情况下, 求 x ^ m % n 最坏情况下复杂度是 2n
        t_ul m = 10000000;        // 在 m < n 的情况下, 求 x ^ m % n 最坏情况下复杂度是 m
        t_ul n = 89999931;

        t_ul a = 1;
        t_ul b = 1;
        t_ul k = 200000000;
        t_ul i = 0;
       
        for (i = 2; i < k; i++) {
                x = a  + b;
                if (x > n) x -= n;
                b = a;
                a = x;
        }

        printf("x = %u\n", x);

        /* next step */
        t_ul t = 1;
        t_ul count = 0;

        do {
                t = t * x;
                while (t >= n) t -= n;
        } while ((++count < m) && (t != 1));
       
        if (count < m) {
                t_ul tm = m % count;
                t = 1;

                while (tm--) {
                        t = t * x;
                        while (t >= n) t -= n;
                }
        }
       
        printf("%u ^ %u mod %u = %u\n", x, m, n, t);
        return 0;
}
[/PHP]

conwood

sorry, 是 log(m)
前面有人提到过

Post by DoDo
这一点我倒是也想到了，不过要求x^m%n也是件痛苦的事。我先寻找使得x^k%n＝1 的k，再通过x^(m%k)%n来得到结果。但是k最大可能大到n－1，这时如果m足够大，那么这一部分的复杂度是n。不知道logk的算法是如何实现的。

代码如下
[PHP]
#include <stdio.h>

typedef unsigned long int t_ul;

int main()
{
        /* x ^ m % n */
        t_ul x = 0;
//        t_ul m = 100000000;        // 在 m > n 的情况下, 求 x ^ m % n 最坏情况下复杂度是 2n
        t_ul m = 10000000;        // 在 m < n 的情况下, 求 x ^ m % n 最坏情况下复杂度是 m
        t_ul n = 89999931;

        t_ul a = 1;
        t_ul b = 1;
        t_ul k = 200000000;
        t_ul i = 0;
       
        for (i = 2; i < k; i++) {
                x = a  + b;
                if (x > n) x -= n;
                b = a;
                a = x;
        }

        printf("x = %u\n", x);

        /* next step */
        t_ul t = 1;
        t_ul count = 0;

        do {
                t = t * x;
                while (t >= n) t -= n;
        } while ((++count < m) && (t != 1));
       
        if (count < m) {
                t_ul tm = m % count;
                t = 1;

                while (tm--) {
                        t = t * x;
                        while (t >= n) t -= n;
                }
        }
       
        printf("%u ^ %u mod %u = %u\n", x, m, n, t);
        return 0;
}
[/PHP]

F&amp;D

我觉得这应该按照一道数学题人工来算，如果写程序算就太简单，没有意思了。下面是俺的程序：

#include<iostream>

int main()
{
        int result = 3%7;
        for(int i = 1;i < 1000;i++)
                result = (result*3)%7;

         std::cout << result << " ";
         std::cout << std::endl;
}

DoDo

18楼的兄弟不要把话说的这么轻松.以求第200000000个Fab数模89999931为例,如果按照直接的方法,先求Fab_200000000就已经导致溢出了

lucifer

再写个无限精度运算的库就可以了
或者用lisp,python之类本身支持这个的语言