首页 > 代码库 > 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%的数据 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++没有使用大数,而且用时超少、、、、
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。