题目链接

F(N)

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 4579 Accepted Submission(s): 1610

Problem Description



Giving the N, can you tell me the answer of F(N)?

Input

Each test case contains a single integer N(1<=N<=10^9). The input is terminated by a set starting with N = 0. This set should not be processed.

Output

For each test case, output on a line the value of the F(N)%2009.

Sample Input

1

2

3

0

Sample Output

1

7

20

Source

HDU 2009-4 Programming Contest

/*

这类题一般有规律，比如是循环，可以化简成等差、等比数列。

此题用程序跑出循环节，在对n取run的模就可以了。

跑循环节的时候也要取模%2009.

*/

#include <set>

#include <map>

#include <cmath>

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

typedef long long  LL;

using namespace std;

LL f[1000000];

int run;//循环节

int n;

void init()//找循环

{

    f[1]=1;

    f[2]=7;

    for(int i=3;;i++)

    {

        f[i]=(f[i-2]+3*i*i-3*i+1)%2009;

        if(f[i]==f[1])

        {

            bool fg=true;

            int k=(i-1)*2;

            int pos=1;

            for(;i<=k;i++)

            {

                f[i]=(f[i-2]+3*i*i-3*i+1)%2009;

                if(f[i]!=f[pos])

                {

                    fg=false;

                    break;

                }

                pos++;

            }

            if(fg)

            {

                run=k/2;

                break;

            }

        }

    }

}

int main ()

{

    init();

    while(scanf("%d",&n),n)

    {

        printf("%lld\n",f[n%run]);

    }

    return 0;

}