Lỗi output khác nhau trong bài tính Fibonacci(n) mod m

minhcanhtu · October 27, 2018, 2:20pm

Hi mọi người.
Em có đang làm 1 bài tập là tính (Fn mod m) với Fn là số fibonacci thứ n (n <= 10^18) và 2 <= m <= 10^3.
Em dùng chu kỳ Pisano: https://vi.wikipedia.org/wiki/Chu_k%E1%BB%B3_Pisano

Ví dụ Fi mod 2 sẽ có dãy chu kỳ là 0 1 1 0 1 1 0 1 1 …
Fi mod 3 sẽ có dãy chu kỳ là 0 1 1 2 0 2 2 1 0 1 1 2 0 2 2 1 …
với dãy lặp 01120221 có độ dài là 8. Khi nó, nếu muốn tính F2015 mod 3 thì mình có 2015 = 251.8 + 7 nên F2015 mod 3 = F7 mod 3 = 1.

Ý tưởng thuật toán của em là sẽ tính mod dần dần Fi cho m với từng lần lặp for. Và khi gặp chuỗi 0 1 (là chuỗi bắt đầu 1 chu trình mới lặp lại) sẽ dừng lại, tìm được chiều dài chu trình.
CODE:

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    long long n;
    int m, length;
    cin >> n >> m;
    vector<int> arr;
    arr.push_back(0);
    arr.push_back(1);
    for (int i = 2; i <= n; ++i) {
        arr.push_back((arr[i - 1] + arr[i - 2]) % m);
        if ((arr[i] == 1) && (arr[i - 1] == 0)) {
            length = i - 1;
            break;
        }
    }
    cout << arr[n % length];
    return 0;
}

Submit lên Coursera thì bị lỗi ở testcase 100 100
Up lên IDEone thì testcase 100 100 cho ra kết quả 1, trong khi codeblocks em cho ra kết quả 75 !

Mọi người có ai biết lỗi này do đâu ko ạ?
Nếu thuật toán em chạy sai cho em xin cách chữa ạ!

Xin cảm ơn !

drgnz · October 27, 2018, 2:34pm

:3 Hình như nó thiếu thiếu ha. Nếu không gặp 0 và 1 thì lúc này length sẽ như thế nào nhể?

minhcanhtu · October 27, 2018, 3:00pm

Em nghĩ là nó sẽ luôn luôn gặp được 0 và 1 mà anh?
Vì chu trình Pisano luôn bắt đầu bằng 0 hoặc 1 và số chu kỳ tối đa là m^2 ?

Copy 1 đoạn trong slide:

rogp10 · October 28, 2018, 4:49am

75 là đáp án (ra đúng nhưng code sai). http://factordb.com/index.php?query=I100+%+100

i <= n chắc chắn là không đúng vì chu kì của modulo 100 là 300 nên length sẽ không được cập nhật, nên câu cuối toạch. Trong trường hợp không cần tính hết chu kì thì phải dùng flag

minhcanhtu · October 28, 2018, 12:22am

Dạ em cảm ơn anh nhiều, code ngu quá ko nghĩ đến trường hợp m^2 > n !

rogp10 · October 28, 2018, 7:30am

Mình xem Pisano từ modulo 2 đến 300 thì chu kì cao nhất là 6 trăm mấy mà không phải m^2 đâu.

Yêu cầu có thể cho tới modulo 99999, lúc đó thuật toán tìm Pisano kém hẳn. Modulo 300 thì phép cộng (và trừ như nhau) rất nhanh nên cũng có thể là một chín một mười.

Thực ra yêu cầu đề bài không phải là tính chu kì Pisano (như PISANO - spoj), nhưng để cho đầy đủ thì link này khá là chi tiết. https://mathematica.stackexchange.com/a/18570