AOJ 2372 - IkaNumber

問題文 : IkaNumber

解法 :
数列の並びを見るとすべて差がfibonacci になっているのが分かる. このpdf の途中に出てくる不等式をそのまま使えば良い.

コード :

#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long lint;

#define MOD (1000000007)

typedef vector<lint> vec;
typedef vector<vec> matrix;

matrix mul(matrix &A, matrix &B)
{
    matrix C(A.size(), vec(B[0].size()));
    
    for (int i = 0; i < A.size(); i++){
        for (int j = 0; j < B[0].size(); j++){
            for (int k = 0; k < A[0].size(); k++){
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
            }
        }
    }
    
    return (C);
}

lint f(lint n)
{
	matrix A(2, vec(2));
	A[0][0] = 1, A[0][1] = 1;
    A[1][0] = 1, A[1][1] = 0;
	
    matrix B(A.size(), vec(A.size()));
    
    for (int i = 0; i < A.size(); i++){
        B[i][i] = 1;
    }
    
    while (n > 0){
        if (n & 1){
            B = mul(B, A);
        }
        A = mul(A, A);
        n >>= 1;
    }
    
    return (B[1][0]);
}

int main()
{
	lint n;
	
	scanf("%lld", &n);
	
	lint lo = 1, hi = 2000000000;
	
	while (lo != hi){
		lint mid = (lo + hi) / 2;
		lint no = (mid / 2) * (mid / 2 + 1);
		
		if (mid & 1) no += (mid + 1) / 2;
		if (no < n) lo = mid + 1;
		else hi = mid;
	}
	
	lint s = ((lo - 1) / 2) * ((lo - 1) / 2 + 1);
	if ((lo - 1) & 1) s += lo / 2;
	lint pos = n - s - 1, rev = (lo - 1) / 2 - pos + 1;
	
	if (lo - pos * 2 + 1 >= (pos + 1) * 2) printf("%lld\n", f(lo - pos * 2 + 1) * f((pos + 1) * 2) % 1000000007);
	else printf("%lld\n", f(rev * 2 + 1) * f(lo - rev * 2 + 2) % 1000000007);
	
	return (0);
}