HDU-2802: F(N)（循环节）

数论

Description

$F(N)-N^3=F(N-2)-(N-1)^3,(N>=3)$
$F(1)=1,F(2)=7.$
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

分析: 这个题需要找循环节，还是看了别人怎么写，不然想不到竟然是循环，先求出循环节，是多少个数一轮循环，将数保存在数组里面，输入n之后模以一个循环节，输出F（n）即可。

• 完整代码：

#include<stdio.h>
#define LL long long
#define mod 2009
LL f[100000];
int main()
{
    LL n,i,repetend;
    f[1]=1,f[2]=7;
    for(i=3;;i++)
    {
        LL t=i%mod;
        f[i]=(f[i-2]+3*t*t-3*t+1)%mod;
        //f[i]=f[i-2]-(i-1)^3+i^3，化简得到上面的式子
        if(f[i-1]==1&&f[i]==7)
            break;
    }
    repetend=i-2; //每4018一次循环
 /* for(i=1;i<=repetend+2;i++)
        printf("%lld ",f[i]);*/
    while(scanf("%lld",&n),n)
    {
        n=n%repetend;
        printf("%lld\n",f[n]);
    }
    return 0;
}