Reafy Sequence

[lky473736]

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n, k;
    cin >> n >> k;

    if (n == 1) {
        if (k == 1)
            cout << 0 << " " << 1 << '\n';
        else if (k == 2)
            cout << 1 << " " << 1 << '\n';
    } 
    else if (n == 2) {
        if (k == 1)
            cout << 0 << " " << 1 << '\n';
        else if (k == 2)
            cout << 1 << " " << 2 << '\n';
        else if (k == 3)
            cout << 1 << " " << 1 << '\n';
    } 
    else {
        set<tuple<double, int, int>> seta;
        seta.insert({0.0, 0, 1});  // 소수, 분자, 분모
        
        int num = 1;

        while (n - 3 >= 0) {
            int numerator = 1;

            while (true) {
                if (seta.find({static_cast<double>(numerator) / n, numerator, n}) == seta.end() 
                    && static_cast<double>(numerator) / n < 0.5) {
                    seta.insert({static_cast<double>(numerator) / n, numerator, n});
                    num++;
                } 
                else {
                    if (static_cast<double>(numerator) / n >= 0.5)
                        break;
                }

                numerator++;
            }

            n--;
        }

        vector<tuple<double, int, int>> left(seta.begin(), seta.end());
        
        if (num + 1 == k)
            cout << 1 << " " << 2 << '\n';
        else if (num + 1 < k)
            cout << get<2>(left[left.size() - (k - num - 1)]) - get<1>(left[left.size() - (k - num - 1)]) << " "
                 << get<2>(left[left.size() - (k - num - 1)]) << '\n';
        else
            cout << get<1>(left[k - 1]) << " " << get<2>(left[k - 1]) << '\n';
    }

    return 0;
}

import sys
import math

# def eratosthenes (M, N) :
#     nums = [0 for i in range (N + 1)]
#     nums.insert(0, 1)

#     for i in range (2, int(math.sqrt(N) + 1)) : # 0, 1은 소수 아님
#         if nums[i] == 0 :
#             for j in range (i + i, N + 1, i) :
#                 nums[j] = 1

#     return nums[M : ]

# primes = eratosthenes(1, 5000)[:-1]
# primes = [idx+1 for idx in range (1, 5000) if primes[idx] == 0]
# print (primes)

n, k = map(int, sys.stdin.readline().split())

if n == 1 :
    if k == 1 :
        print(0, 1)
        
    elif k == 2 :
        print(1, 1)

elif n == 2 :
    if k == 1 :
        print(0, 1)
        
    elif k == 2 :
        print(1, 2)
        
    elif k == 3 :
        print(1, 1)
        
else :
    seta = set()
    seta.add ((0, 0, 1)) # 소수, 분자, 분모
    
    num = 1
    
    while n - 3 >= 0 :
        numerator = 1
        
        while True :  
            if (numerator/n, numerator, n) not in seta and numerator/n < 0.5 :
                seta.add ((numerator/n, numerator, n))
                num += 1
            
            else : 
                if numerator/n >= 0.5 :
                    break
                
            numerator += 1
            
        n -= 1
        
    # print (seta)
    left = sorted(list(seta), key = lambda x : x[0])
    # print (left)
    
    if num + 1 == k : 
        print (1, 2)
        
    elif num + 1 < k : 
        # print (left[-(k-num-1)])
        print (left[-(k-num-1)][2]-left[-(k-num-1)][1], left[-(k-num-1)][2])
        
    else : 
        print (left[k-1][1], left[k-1][2])
        
    # print (seta)