취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 10425번 문제인 피보나치 인버스이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/10425

적절한 ${10}^K$로 첫 10만개의 피보나치 수를 나눈 나머지를 얻어보면 (첫 두 수를 제외하고) 이 값들이 서로 다름을 확인할 수 있다.

따라서 이를 이용해 첫 10만개의 수를 ${10}^K$로 나눈 나머지를 map 등을 이용해 순서와 대응시켜 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <map>
using namespace std;
typedef long long ll;

int T;
ll A = 1, B = 1;
map<ll, int> mp;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    for (int k = 2; k < 100001; k++) {
        A += B;
        swap(A, B);
        if (B > 99999999999999999LL) B -= 100000000000000000LL;
        mp[A] = k;
    }
    
    cin >> T;
    while (T--) {
        string s; cin >> s;
        ll val = 0;
        for (auto &l:s) {
            val = val * 10 + (l - '0');
            val %= 100000000000000000LL;
        }
        cout << mp[val] << '\n';
    }
}