FZU 2125 简单的等式

/*
思路:对于给定的m，S(x, m) 的范围可以确定最大值。
S(x, m) = n / x - x,函数递减，所以遍历x的时候，从sqrt(n) 遍历到S(X, m)递增到最大值过程中得到的满足条件的x的最小值即为ans.
*/

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <cmath>
#define maxn 1e9
using namespace std;

long long num[20];

void init() { // 计算maxn表示成进制时，各位之和相加的最大值
    for (int i=2; i<=16; ++i) {
        long long st = 1;
        int ans = 0;
        while(st <= maxn) {
            st *= i;
            ans += i-1;
        }
        num[i] = ans-i+1;
    }
}

int get(long long x, int m) { // 计算x写成m进制各位相加之和
    long long st = x;
    int ans = 0;
    while(st) {
        ans += st % m;
        st /= m;
    }
    return ans;
}

int main() {
    init();
    int t;
    scanf("%d", &t);
    while(t--) {
        long long n;
        int m;
        scanf("%I64d%d", &n, &m);
        long long st = (long long)sqrt(n);
        long long ans = -1;

        for (long long i=st; i>0; --i) {
            if (n / i - i > num[m]) break;
            if (n%i != 0) continue;
            if (n / i - i == get(i, m)) {
                ans = i;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}