[PS] 백준 1882번: 분수 찾기, 30449번: Reafy 수열

분수 찾기  Reafy 수열

 

이 링크 참고해서 어거지로 풀었다.

요약하자면, 이런식으로 a/b, c/d를 알 때 다음항인 p/q를 알 수 있다는 뜻이다. 이걸로 Reafy 수열은 간단하게 해결.

 

근데 이걸로 분수 찾기를 하려고 하니 너무 당연하게도 시간초과가 났다.

Reafy 수열의 다른사람들 코드를 보니깐

int find_pos(int a, int b) {
    int ret = 0;
    for(int i = 1; i <= N; i++) arr[i] = a * i / b;
    for(int i = 1; i <= N; i++) {
        ret += arr[i];
        for(int j = i * 2; j <= N; j += i) {
            arr[j] -= arr[i];
        }
    }
    return ret;
}

이런식으로 a/b 전에 기약분수가 몇개나 있을지 찾을수가 있더라.

Reafy 수열을 풀 때, 에라토스테네스의 체 느낌으로, i 이하인 기약분수 수열을 만들때, 가능한 i 이하의 분수를 전부 만들어두고, 2부터 i - 1까지 순회하면서 1/2 빼고 1/3빼고 2/3빼고... 하는 시도는 했지만 당연히 시간이 너무 많이걸려서 포기했는데, 이런식으로 개수찾는데 쓰일 수 있겠구나 싶었다.

 

무튼 분수 찾기는 그냥 이거 활용해서 22토막내가지고 Reafy 수열 풀듯 똑같이 풀어서 야매로 냈다.

다른 사람 코드들 보니 정해는 스턴-브로콧 트리를 활용해서 푸는 방식 같던데, 조만간 스턴-브로콧 트리를 공부해서 다시 제출해야겠다.

 

Reafy 수열

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

#define FOR(i, n) for(int i = 0; i < int(n); i++)
#define FORL(e, s) for(auto &e : s)
#define endl "\n"
#define vi vector<int>

#define pii pair<int, int>
#define vp list<pii>
int N, K;

int main() {
    cin >> N >> K;
    
    int a = 0, b = 1, c = 1, d = N;
    if (K == 1) { cout << a << " " << b << endl; return 0; }
    if (K == 2) { cout << c << " " << d << endl; return 0; }
    for (int _ = 3; _ <= K; _++) {
        int k = (N + b) / d;
        int p = k * c - a;
        int q = k * d - b;
        a = c, b = d;
        c = p, d = q;
    }
    cout << c << " " << d << endl;

    return 0;
}

 

 

분수 찾기

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

#define FOR(i, n) for(int i = 0; i < int(n); i++)
#define FORL(e, s) for(auto &e : s)
#define endl "\n"
#define vi vector<int>

#define pii pair<int, int>
int N, K;

#define ESIZE 23
pii eights[ESIZE] = {{0, 1}, {1, 8}, {1, 7}, {1, 6}, 
                     {1, 5}, {1, 4}, {2, 7}, {1, 3}, 
                     {3, 8}, {2, 5}, {3, 7}, {1, 2}, 
                     {4, 7}, {3, 5}, {5, 8}, {2, 3}, 
                     {5, 7}, {3, 4}, {4, 5}, {5, 6}, 
                     {6, 7}, {7, 8}, {1, 1}};

int arr[40001];
int find_pos(pii p) {
    auto [a, b] = p;
    int ret = 0;
    for(int i = 1; i <= N; i++) arr[i] = a * i / b;
    for(int i = 1; i <= N; i++) {
        ret += arr[i];
        for(int j = i * 2; j <= N; j += i) {
            arr[j] -= arr[i];
        }
    }
    return ret;
}

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

    if (K == 1) { cout << 1 << " " << N << endl; return 0; }
    if (N <= 5000) {
        int a = 0, b = 1, c = 1, d = N;
        for (int _ = 2; _ <= K; _++) {
            int k = (N + b) / d;
            int p = k * c - a;
            int q = k * d - b;
            a = c, b = d;
            c = p, d = q;
        }
        cout << c << " " << d << endl;
        return 0;
    }
    
    int pos = 0;
    int l, r;
    FOR(i, ESIZE - 1) {
        l = find_pos(eights[i]), r = find_pos(eights[i + 1]);
        if (l == K) { cout << eights[i].first << " " << eights[i].second << endl; }
        if (l < K && K < r) { pos = i; break; }
    }

    auto [a, b] = eights[pos]; auto [c, d] = eights[pos + 1];
    while(true) {
        pii p = {a + c, b + d};
        if (p.second > N) break;
        c = p.first, d = p.second;
    }
    
    for (int _ = l + 1; _ < K; _++) {
        int k = (N + b) / d;
        int p = k * c - a;
        int q = k * d - b;
        a = c, b = d;
        c = p, d = q;
    }
    cout << c << " " << d << endl;
    return 0;
}