hdu--5351--MZL's Border

表示看这篇博客后找到了思路:

http://blog.csdn.net/queuelovestack/article/details/47291195

补充一下数据,方便观察规律

m  LBorderm  m-LBorder  fibn

1          0               1          1

2          0               2          1

3          1               2          2

4          1               3          3

5          2               3          5

6          3               3          8

7          2               5          13

8          3               5          21

9          4               5          34

10        5               5          55

11        6               5          89

12        4               8          144

13        5               8          233

14        6               8          377

仔细观察一下,便会得出这样一个结论:

当我们找到第一个i满足m+1<|fibi|时,LBorderm=m-|fibi-2|(|fibi-2|表示斐波那契串fibi-2的长度)

附上代码:

 import java.util.*;
 import java.math.*;
 public class Main {

     public static void main(String[] args) {

         BigInteger ar[]=new BigInteger[1000];
         ar[1]=BigInteger.valueOf(1);
         ar[2]=BigInteger.valueOf(2);
         for(int i=3;i<1000;++i){
             ar[i]=ar[i-1].add(ar[i-2]);
         }
         Scanner cin=new Scanner(System.in);
         int t=cin.nextInt();
         while(t-- >0){
             int n=cin.nextInt();
             BigInteger m=cin.nextBigInteger();
             for(int i=1;i<1000;++i){
                 if(m.compareTo(ar[i]) <0 && m.compareTo(ar[i-1]) >=0){
                     m=m.subtract(ar[i-2]).mod(BigInteger.valueOf(258280327));  ;
                     break;
                 }
             }
             System.out.println(m);
         }
     }
 }
  
上一篇:Silverlight中使用MVVM(2)-(提高)


下一篇:android API之android.text.TextWatcher