백준 27892 - 특별한 큰 분수 (C++)

문제

• 문제 링크

  
   BOJ 27892 - 특별한 큰 분수 
  

• 문제 요약

분수의 $0$초일 때 높이가 주어진다.
문제에 정의된 규칙을 따라 높이가 변화할 때, $N$초에서의 분수의 높이를 구해보자.

• 제한

TL : $1$ sec, ML : $512$ MB




$0 ≤ x_0, N ≤ 10^{18}$

알고리즘 분류

• 수학(math)
• 자료 구조(data structures)
• 해시를 사용한 집합과 맵(hash _ set / map)

풀이

브루트포스로 이런저런 $x_0$에 대해 $N=1,000$으로 잡고 그 변화를 출력해 보니, 한가지 사실을 관찰할 수 있었다.
모든 수들이 빠른 속도로 감소 하다가 임의의 사이클로 수렴 하게 되는 것이었다.
그렇게 믿음을 갖고 제출해 $AC$를 받았다.

엄밀한 풀이는 에디토리얼 을 참고하자.

전체 코드

#include<bits/stdc++.h>
#define ll long long
using namespace std;
 
vector <ll> V;
set <ll> S;
 
ll f(ll x) { return (x & 1 ? (x << 1) : (x >> 1)) ^ 6; }
int main()
{
    ll a, n; cin >> a >> n;
    while(n--)
    {
        a = f(a);
        if (S.count(a)) break;
        S.insert(a);
    }
    if (!~n) cout << a, exit(0);
 
    ll len(1), j(f(a));
    for (V.push_back(a); j ^ a; len++)
        V.push_back(j), j = f(j);
    cout << V[(n + len) % len];
}

comment

끝