436.cpp

#include <iostream>
#include <algorithm>
#include <cstdint>
#include <cassert>
#include <cstdlib>
#include <set>

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, count_k_in_base(number, digit, 2)};
    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)});
    }
    int64_t base = number / digit - 1;
    if (digit != 0 && number % digit == 0 && base >= 2) {
        answ = std::max(answ, Answer{base, count_k_in_base(number, digit, base)});
    }
    return answ;
}
/*
void test() {
    for (int number = 1; number < 10; ++number) {
        for (int digit = 0; digit < 10; ++digit) {
            std::cout << "solve(" << number << "," << digit << ")=" << solve(number, digit) << std::endl;
        }
    }
    std::exit(0);
}
*/
int main() {
    //test();

    std::set<int64_t> input{49, 9, 6, 3, 32, 781, 777, 754000, 1771561};

    int64_t number;
    int digit;
    std::cin >> number >> digit;
    if (input.find(number) == input.end()) {
        assert(100*1000*1000 <= number && number < 1000*1000*1000);
        assert(number >= 775000000);
    }
    auto answ = solve(number, digit);
    assert(answ.base >= 2);
    if (answ.count != 0) {
        assert(count_k_in_base(number, digit, answ.base) == answ.count);
    }
    std::cout << answ << std::endl;
    return 0;
}