1022. Fib数列
Description
定义Fib数列：1,1,2,3,5,8,13,…
求第N项除以2010的余数
Input Format
输入仅一行，为一个整数N
Output Format
输出仅一行，为第N项除以2010的余数
Sample Input
3
Sample Output
2
Limits:
对于70%的数据 N≤1,000,000
对于100%的数据 N≤210,000,000,000
这道题最让人着急的是数太大了，而且不可以使用递归，这种方法会暴栈，但是java里有大数类，天然的优势，代码如下：
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
private static Scanner in;
public static void main(String[] args) {
in = new Scanner(System.in);
long n=in.nextLong();
Main m =new Main();
BigInteger res =m.fib(n);
System.out.print((res.divideAndRemainder(new BigInteger("2010")))[1]);
}
BigInteger fib(long n){
if(n==1 || n==2){
return new BigInteger("1");
}else{
BigInteger pnum=new BigInteger("1");
BigInteger cnum=new BigInteger("1");
for(int i=3;i<=n;i++){
cnum= cnum.add(pnum);
pnum =cnum.subtract(pnum);
}
return cnum;
}
}
}
但是很令人忧伤的是即使使用大数类保存数据，即使循环只有n次，也会超时、、、、、无奈的只好百度一下发现，fib数列对2010取余后竟是周期数列，周期是2040、、
所以更改代码如下：
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
private static Scanner in;
public static void main(String[] args) {
in = new Scanner(System.in);
long n=in.nextLong();
Main m =new Main();
if(n%2040==0){
System.out.print(0);
}else{
BigInteger res = m.fib(n%2040);
System.out.print((res.divideAndRemainder(new BigInteger("2010")))[1]);
}
}
BigInteger fib(long n){
if(n==1 || n==2){
return new BigInteger("1");
}else{
BigInteger pnum=new BigInteger("1");
BigInteger cnum=new BigInteger("1");
for(int i=3;i<=n;i++){
cnum= cnum.add(pnum);
pnum =cnum.subtract(pnum);
}
return cnum;
}
}
}
这就可以通过了、、、、这是java的福利
但是，有大神用C++没有使用大数，而且用时超少、、、、