9471번

9471번 - 피사노 주기

2749번 피보나치 수 3 문제와 아주 똑같이 풀면 된다.

2749번 에서는 나머지를 구했지만, 여기서는 반복되는 구간의 길이만 구하면 된다.

설명은 2749번과 동일

<정답 코드>

#include<iostream>
#include<vector>
using namespace std;
 
//const long long  mod = 1000000;
 
int main()
{
    int P;
    scanf("%d", &P);
    while (P--)
    {
        vector<long long> num;
        long long  N;
        long long mod;
 
        scanf("%lld %lld", &N,&mod);
 
        num.push_back(0);
        num.push_back(1);
 
        long long i = 1;
        long long j = 0;
        long long flag = -1;
        bool cycle = false;
 
        while (!cycle)
        {
            i++;
            long long  temp = (num[i - 1] % mod + num[i - 2] % mod) % mod;
            num.push_back(temp);
 
            if (temp == num[j++])
            {
                if (flag == -1)
                {
                    flag = i - 1;
                }
            }
            else
            {
                flag = -1;
                j = 0;
            }
 
            if (j == flag)
            {
                cycle = true;
            }
        }
 
        long long  size = j + 1;
        //long long rest = N % size;
 
        //printf("%lld\n", num[rest]);
        printf("%lld %lld\n",N, size);
    }
 
    
 
    return 0;
}