首页 > 代码库 > acm 之fib数列——java

acm 之fib数列——java

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%的数据 N1,000,000

对于100%的数据 N210,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++没有使用大数,而且用时超少、、、、