Hello everyone , I'm a bubble , The purpose of bringing you a daily question is to better practice the algorithm , Our daily question is to let you practice all kinds of questions , Familiar with various question types , A year later , Transform into a different self ！

Welcome to focus on the likes collection ️ Leaving a message.

️ ： love C/C++ And algorithm learning , Cloud computing, etc , Looking forward to communication ！

The author's level is limited , If an error is found , Please let me know , Thank you very much ！

University algorithm learning community ：https://bbs.csdn.net/forums/Suanfa

Join the army of brushing questions together , You can also join an exclusive inner volume group , There are a lot of benefits and a lot of big guys ！

Catalog

Today's topic ： The starting point of the end  

Title Description

Input format

Output format

Topic analysis

Problem solving report ：

1. Ideas

2. Code

Today's topic ： The starting point of the end  

The starting point of the end
Finally write down the period
Finally we say goodbye
Finally, we are back to the origin
……

One by one OIer My competitive career always starts with NOIp Start , Most of them are also in a NOIp In the end , It's like reincarnation is on again and again .
If the NOIp Is your starting point , Then I wish you OI Life is as gorgeous as summer flowers .
If the NOIp It's your destination , Then I wish you OI Memories are as bright as stars .
Maybe this is your last time playing in the Los Angeles Valley , Maybe not. .
however , in any case , I wish you in the game in a week , Good luck .

Of course , This question is also related to reincarnation .

Title Description

The well-known fiboracci sequence is calculated in this way

That is to say  0, 1, 1, 2, 3, 5, 8, 13 \cdots0,1,1,2,3,5,8,13⋯, Each is the sum of the first two .

Small F Find out , If each pair of fiboracci numbers is arbitrarily greater than  11  The positive integer  MM  When taking the mold , A sequence of numbers produces a loop .

Of course , Small F I soon understood , because (\mathrm{fib}(n - 1) \bmod Mfib(n−1)modM) and (\mathrm{fib}(n - 2) \bmod M)fib(n−2)modM)  Only up to M2  Species value , So in  M ^ 2M2  There must have been a cycle after this calculation .

Even more generally , We can prove that , Whatever modulus is taken  M, Final die  M  The next fiboracci sequence will be ,0,1,⋯.

Now? , Give you a module  M, Please find out the smallest n>0, bring M = 1fib(n)modM=0,fib(n+1)modM=1.

Input format

Enter a positive integer per line  M.

Output format

Output a positive integer line by line  n.

 

Topic analysis

questions ：️️

The topic involves algorithms ： Recurrence , violence .

ps： Capable partners can try to optimize their own code or solve more than one problem , This can comprehensively improve their algorithm ability

Problem solving report ：

1. Ideas

use longlong Prevent explosion Then just direct violence simulation

2. Code

#include<stdio.h>
long long arr[10000002];
long long m;
long long fib(long long x)
{
    if(arr[x])
    {
        return arr[x];
    }
    if(x==1||x==2)
    {
        return arr[x] = 1 % m;
    }
    else
    {
        return arr[x]=(fib(x-1)+fib(x-2))%m;
    }
}
int main()
{
    scanf("%lld",&m);
    long long i=1;
    while(fib(i)!=0||fib(i+1)!=1)
    {
        i++;
    }
    printf("%lld",i);
    return 0;
}