AOJ 2372 IkaNumber

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2372

解法

問題文を言い換えると，フィボナッチ数同士の積で表される数で K 番目に小さいものは何か？という問題です．
実験すればなんとなく規則性が見えてきます．
自分は fib(n) * fib(m) (1 <= n, m <= 10 ぐらい）の表を出力したらわかりました．
小さい順から斜めにずら～っとならんだ感じの表が得られます．
あとは何番目の斜めの場所にあるか探索して，いい感じにインデックスを合わせるだけです．
コーナーケースはないですが，ちゃんと手で確かめないとインデックスがずれやすいかも．

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using matrix = vector<vector<ll>>;

constexpr ll M = 1e9 + 7;

matrix mul(matrix a, matrix b) {
    matrix res(a.size(), vector<ll>(b[0].size()));
    for(int i = 0; i < (int)a.size(); ++i) {
        for(int k = 0; k < (int)b.size(); ++k) {
            for(int j = 0; j < (int)b[0].size(); ++j) {
                (res[i][j] += a[i][k] * b[k][j]) %= M;
            }
        }
    }
    return res;
}

matrix modpow(matrix x, ll n) {
    matrix res(x.size(), vector<ll>(x.size()));
    for(int i = 0; i < (int)x.size(); ++i) {
        res[i][i] = 1;
    }
    
    while(n > 0) {
        if(n & 1) {
            res = mul(res, x);
        }
        x = mul(x, x);
        n >>= 1;
    }
    return res;
}

ll fib(int n) {
    matrix A(2, vector<ll>(2));
    A[0][0] = A[0][1] = 1;
    A[1][0] = 1;
    matrix b(2, vector<ll>(1));
    b[0][0] = b[1][0] = 1;
    return mul(modpow(A, n - 1), b)[0][0];
}

int main() {
    ll K;
    cin >> K;

    ll lb = 0, ub = 1e10;
    while(ub - lb > 1) {
        ll m = (lb + ub) / 2;
        if(m * (m + 1) < K) {
            lb = m;
        } else {
            ub = m;
        }
    }
    K -= lb * (lb + 1);
    int x = lb * 2 + (K - 1) / ub + 1;
    if(K > ub) {
        K -= ub;
    }
    int y = 0;
    if(K <= (ub + 1) / 2) {
        y = 2 * K - 1;
    } else {
        y = ub - (ub & 1) - (K - (ub + 1) / 2 - 1) * 2;
    }

    cout << (fib(y) * fib(x - y + 1) % M) << endl;
}

感想

実験は大切だと再認識する問題．

これは一般的な話ですが，闇雲に実験しても（無駄ではないですが）いい知見が得られないことも多くて，実験するのにも経験が必要だなあと感じます．