HDOJ 5351 MZL's Border의 법칙 찾기

   
   
   
   

    
    
    
    2
4 3
5 5
   
   
   
   

   
   
   
   

    
    
    
    1
2
   
   
   
   

import java.util.*;
import java.math.*;

public class Main {

	final BigInteger mod = BigInteger.valueOf(258280327);
	
	BigInteger fib[] = new BigInteger[1100];
	BigInteger sum[] = new BigInteger[1100];
	BigInteger all[] = new BigInteger[1100];
	
	void init() {
		
		fib[1]=BigInteger.ONE; fib[2]=BigInteger.ONE;
		sum[1]=BigInteger.ZERO; sum[2]=BigInteger.ONE;
		for(int i=3;i<=1010;i++) {
			fib[i]=fib[i-1].add(fib[i-2]);
			sum[i]=sum[i-1].add(fib[i]);
		}
		all[1]=BigInteger.valueOf(2);
		for(int i=2;i<=1010;i++) {
			all[i]=all[i-1].add(fib[i].multiply(BigInteger.valueOf(2)));
		}
	}
	
	void solve(BigInteger x) {
		if(x.compareTo(BigInteger.valueOf(2))<1) {
			System.out.println(0);
			return ;
		}
		
		for(int i=1;i<=1000;i++) {
			int k=x.compareTo(all[i]);
			if(k==1) continue;
			else if(k==0) {
				System.out.println(sum[i].mod(mod));
				return ;
			}
			else
			{
				BigInteger y = x.subtract(all[i-1]);
				if(y.compareTo(fib[i])>0) {
					y=y.subtract(fib[i]);
				}
				System.out.println(y.add(sum[i-1]).mod(mod));
				return ;
			}
		}
	}
	
	Main(){
		
		init();
		Scanner in = new Scanner(System.in);
		
		int T_T;
		T_T=in.nextInt();
		while(T_T-->0) {
			int n=in.nextInt();
			BigInteger m = in.nextBigInteger();
			solve(m);
		}
	}
	
	public static void main(String[] args) {
		new Main();
	}
}