Problem description

Fibonacci The recurrence formula of sequence is :Fn=Fn-1+Fn-2, among F1=F2=1.

When n The larger the ,Fn It's also very large. , Now we want to know ,Fn Divide 10007 What is the remainder of .

Input format
Input contains an integer n.
Output format
Output one line , Contains an integer , Express F n Divide 10007 The remainder of .

explain : In the subject , The answer is demand Fn Divide 10007 The remainder of , So we just need to work out the remainder , You don't have to work out Fn The exact value of , Then divide the result of the calculation by 10007 Take the remainder , It is often easier to calculate the remainder directly than to calculate the original number first and then take the remainder .

The sample input
10
Sample output
55
The sample input
22
Sample output
7704
Data scale and agreement
1 <= n <= 1,000,000.
#include"stdio.h"
int f(int n)
{
int x1=;
int x2=;
int sum=;
if(n==||n==)
return ;
int i;
for(i=;i<=n;i++)
{
sum=x1+x2;
if(sum>)
sum%=;
x1=x2;
x2=sum;
}
return sum;
} int main()
{
int n;
scanf("%d",&n);
printf("%d\n",f(n));
return ;
}

Fibonacci More articles on sequence of numbers

  1. Fibonacci Sequence algorithm analysis

    /************************************************* * Fibonacci Sequence algorithm analysis ****************************** ...

  2. Variable length Fibonacci The sequence

    Original title : Write a recursive program that extends the range of the Fibonacci sequence.  The Fibonacci sequ ...

  3. Entry training Fibonacci The sequence

      Entry training Fibonacci The sequence   The time limit :1.0s   Memory limit :256.0MB Problem description Fibonacci The recurrence formula of sequence is :Fn=Fn-1+Fn-2, among F1=F2=1. When n The larger the , ...

  4. fibonacci Sequence and its application

    fibonacci Sequence and its extension fibonacci Calculation fibonacci A sequence of numbers is 0,1,1,2,3,5,8,13,21…… So the sequence of natural numbers , From the first 3 Items begin to satisfy f(n)=f(n-1)+f(n-2): ...

  5. 【 Programming topics 】 subject : Definition Fibonacci The sequence Input n, Use the quickest method to find the number of the sequence of n term .

    The first 19 topic ( Array . recursive ): subject : Definition Fibonacci The sequence is as follows :/ 0 n=0f(n)= 1 n=1/ f(n-1)+f(n-2) n=2 Input n, Use the quickest method to find the number of the sequence of n term . Ideas : recursive ...

  6. Fast exponentiation of matrix multiplication codevs 1732 Fibonacci The sequence 2

    1732 Fibonacci The sequence 2   The time limit : 1 s   Space restriction : 128000 KB   Question level : diamond Diamond Answer key   View the run results     Title Description  Description stay “ ...

  7. Fast exponentiation of matrix multiplication codevs 1250 Fibonacci The sequence

    codevs 1250 Fibonacci The sequence   The time limit : 1 s   Space restriction : 128000 KB   Question level : diamond Diamond   Title Description  Description Definition :f0=f1=1 ...

  8. Blue Bridge Cup Entry training Fibonacci The sequence ( Water problem , Fibonacci sequence )

    Entry training Fibonacci The sequence The time limit :1.0s   Memory limit :256.0MB Problem description Fibonacci The recurrence formula of sequence is :Fn=Fn-1+Fn-2, among F1=F2=1. When n The larger the ,Fn Also not ...

  9. 【wikioi】1250 Fibonacci The sequence ( Matrix multiplication )

    http://wikioi.com/problem/1250/ I won't say how watery it is . 0 1 1 1 Matrix fast power #include <cstdio> #include <cstri ...

  10. Frogs jump the steps (Fibonacci The sequence )

    problem A frog can jump up at a time 1 Stepped steps , You can jump on it 2 level . Ask the frog to jump on one n How many jumps are there in the steps . Ideas When n=1 when , There's only one way to jump , And f(1)=1, When n=2 when , There are two ways to jump , And f(2)=2, When n= ...

Random recommendation

  1. Mysql Basics 1

    Mysql int integer float decimal double decimal varchar(20) character string bit Boolean data datetime Date time type text Long text money Deposit money image Save binary data Count ...

  2. sql How to filter duplicate records

    distinct : select distinct ID from table1

  3. Win 7 How to deny all permissions to all removable storage devices

    stay Windows 7 in , We can deny access to any removable storage class . Now let me teach you how to enable “ All removable storage classes : Deny all permissions ” Strategy , The specific operation steps are as follows : step / Method Type... In the start search box “gpedi ...

  4. Maven Learning summary ( One )——Maven introduction

    The original blog post comes from :http://www.cnblogs.com/xdp-gacl/p/3498271.html thank ! One .Maven Basic concepts of Maven( Translated into " Experts "," ...

  5. 【 Weak province Hu ce 】Round #7 Rectangle Problem solving report

    orz PoPoQQQ The divine theme of . My idea is : Maintain one for every height $01$ Sequence , It's about maintaining a $Map[i][j]$ Matrix , then $Map[i][j]$ It means the first one $i$ Is the height of the column ...

  6. Multithreading -Timer Reentrant

    Multithreading Timer Reentry problem Due to the use of multithreaded timers , It will appear if one Timer Processing is not complete , When it's time, the next one will still happen , This leads to reentry . The usual way to deal with reentry is to lock , But for Timer But you can't just do it ...

  7. Team work 7-Beta Version sprint plan and arrangement

    a. The next stage needs to be improved and perfected Right part bug Modification of , It is mainly the problem of page jump when not logged in and the prevention of injecting query into the database . b. What's new in the next phase 1. Activity page , Prompt discount information, etc . 2. Merchants modify discount information 3. ...

  8. @Html.LabelFor How to add CSS style

    The pattern is bootstrap. I want to adjust the style of one of the controls separately , Maybe this shape . @Html.LabelFor(m => m.DerivationRate, new { @class = &q ...

  9. 【BZOJ2749】【HAOI2012】 The aliens [ Euler function ]

    The aliens Time Limit: 3 Sec  Memory Limit: 128 MB[Submit][Status][Discuss] Description Input   Output Output te ...

  10. MySql Installation and password setting, etc

    1.MySQL Download and install . Simple application and directory introduction 1. Download and install windows10 Of :https://www.cnblogs.com/clschao/articles/9916971.html linux ...