436.cpp

#include <iostream>
#include <algorithm>
#include <cstdint>

struct Answer {
    int64_t base;
    int count;
};

bool operator>(const Answer& a, const Answer& b) {
    return a.count > b.count || (a.count == b.count && a.base < b.base);
}

bool operator<(const Answer& a, const Answer& b) {
    return b > a;
}

std::ostream& operator<<(std::ostream& os, Answer answ) {
    return os << answ.base << " " << answ.count;
}

int count_k_in_base(int64_t number, int digit, int64_t base) {
    int count = 0;
    while (number > 0 && number % base == digit) {
        number /= base;
        count++;
    }
    return count;
}

Answer solve(int64_t number, int digit) {
    if (digit > number) {
        return Answer{2, 0};
    }
    if (digit == number) {
        return Answer{number+1, 1};
    }
    Answer answ{2, 0};
    for (int64_t base = std::max(2, digit+1); base * base <= number; ++base) {
        answ = std::max(answ, Answer{base, count_k_in_base(number, digit, base)});
    }
    if (digit != 0 && number % digit == 0) {
        answ = std::max(answ, Answer{number / digit-1, 2});
    }
    return answ;
}

int main() {
    int64_t number;
    int digit;
    std::cin >> number >> digit;
    std::cout << (solve(number, digit)) << std::endl;
    return 0;
}