HDU 2802 F(N)(简单题,找循环解)

题目链接

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

HDU 2802 F(N)(简单题,找循环解)

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;
}
上一篇:HDU 6090 Rikka with Graph —— 2017 Multi-University Training 5


下一篇:线性分式变换(linear fractional transformation)