杭电2802F(N)

F(N)

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

Total Submission(s): 4073    Accepted Submission(s): 1430

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  

Recommend lcy   |   We have carefully selected several similar problems for you:   2807  2803  2804  2800  2806   

输出循环节就行了，公式很难推的：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
__int64 a[100000],i,j,k,l,m,n;
void ac()
{
	for(i=3;i<=4020;i++)
	a[i]=(a[i-2]-(i-1)*(i-1)*(i-1)+i*i*i)%2009;
}
int main()
{
	a[1]=1;
	a[2]=7;
	ac();
	while(scanf("%I64d",&n),n)
//		for(i=3;i<=100000;i=i+2)//输出循环节 
//		if(a[i]==1)
//		break;
//		printf("%I64d\n",i-1);
//		for(i=4;i<10000;i=i+2)
//		if(a[i]==7)
//		break;
//		printf("%I64d\n",i-2);
	printf("%I64d\n",a[n%4018]);
		//printf("%I64d\n",a[4018]);
}