CODEWITHSUNDEEP
c++
UTPAL
UTPAL

Reputation: 31

Fibonacci Number modulo m

Task: Given two integers n and m, output Fn mod m (they is, the remainder of Fn when divided by m).

My Code:

#include <iostream>
#include <vector>

using namespace std;

long long get_pisano_period(long long m)
{
    long long a = 0, b = 1, c;
    for (int i = 0; i < m * m; i++)
    {
        c = (a + b) % m;
        a = b;
        b = c;
        if (a == 0 && b == 1)
            return i + 1;
    }
}

long long calc_fib(long long n)
{
    vector<long long> nums(n + 1);
    nums.at(0) = 0;
    nums.at(1) = 1;
    for (long long i = 2; i < nums.size(); i++)
    {
        nums.at(i) = nums.at(i - 1) + nums.at(i - 2);
    }
    return nums.at(n);
}

long long solve(long long n, long long m)
{
    long long r = n % get_pisano_period(m);
    return (calc_fib(r) % m);
}

int main()
{
    long long n, m;
    cin >> n >> m;

    cout << solve(n, m) << endl;
    return 0;
}

My code is working for some cases(small numbers). Can anyone suggest to me, What changes should I make to run this? 

Input:
239
1000

Output:
-191

You can see I am supposed to get 161 as output.

Upvotes: 0

Views: 118

Answers (1)

Pathlessbark8
Pathlessbark8

Reputation: 73

I tried what @idclev463035818 said and this seems to work. Try it,

# include <iostream>
# include <vector>

using namespace std;

long long get_pisano_period(long long m)

{
    long long a = 0, b = 1, c;
    for (long long i = 0; i < m * m; i++)
    {
        c = (a + b) % m;
        a = b;
        b = c;
        if (a == 0 && b == 1)
            return i + 1;
    }
}

long long calc_fib(long long n, long long m)
{
    vector<long long> nums(n + 1);
    nums.at(0) = 0;
    nums.at(1) = 1;
    long long maximum = get_pisano_period(m);
    for (long long i = 2; i < nums.size(); i++)
    {
        nums.at(i) = (nums.at(i - 1)%m + nums.at(i - 2)%m)%m;
    }
    return nums.at(n);
}

int main()
{
    long long n, m;
    cin >> n >> m;

    cout << calc_fib(n, m) << endl;
    return 0;
}

Upvotes: 1

Related Questions