Учитывая два целых числа ? и ?, выведите Фибоначчи (?) mod ? - PullRequest
Новая
       16

Учитывая два целых числа ? и ?, выведите Фибоначчи (?) mod ?

0 голосов
/ 25 апреля 2020

Я пытался решить этот вопрос из задания: 

Input Format. The input consists of two integers ? and ? given on the same line (separated by a space).

Constraints. 1 ≤ ? ≤ 10^14, 2 ≤ ? ≤ 10^3.

Output Format. Output ?? mod ?.

Sample 1.
Input: 239 1000
Output: 161

Sample 2.
Input: 2816213588 239
Output: 151

Учитывая, что: для любого целого числа 2 ≥ 2 последовательность ?? mod ? равна periodi c. Период всегда начинается с 01 и известен как период Пизано. Я написал код, чтобы найти длину периода Пизано и затем вычислить (n % period) % m. Мой подход заключается в следующем: 

#include<bits/stdc++.h>

#define mx 1002
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;
long long f[mx];
long long temp;
int main()  {
    IOS;
    long long n,m;
    cin >> n >> m;
    f[0]=0; f[1]=1;
    for(int i=02; i<mx; i++) {
        f[i]=((f[i-1]%m)+(f[i-2])%m)%m;
        if(f[i]==1 && f[i-1]==0)    {
                temp=i-1;
                break;
        }
    }
    n=n%temp;
    cout << f[n] << endl;
}

Проблема заключается в том, что код не работает для некоторых определенных c значений m - например, m = 500,1000,999. Хотя это работает для m = 499 501 1001 998, et c. Например - контрольный пример 239 500 не сработает. В чем причина этого? Кроме того, не могли бы вы предложить метод решения этой проблемы.

Кроме того, не могли бы вы сказать мне - к какому числу я должен запустить l oop, чтобы обязательно найти повторяющийся шаблон? Как здесь, я бегу от l oop до mx = 1002.

...