#include<bits/stdc++.h> usingnamespace std; int t; int n, k; inlineintgetsum(int n, int b){ int tot = 0; while (n) { tot += n % b; n /= b; } return tot; } intmain(){ freopen("base.in", "r", stdin); freopen("base.out", "w", stdout); scanf("%d", &t); while (t--) { scanf("%d%d", &n, &k); if (k == n) { puts("1"); continue; } int tmp = sqrt(n); int ans = __builtin_popcount(n); if (k == n - 1) ans = min(ans, 2); for (int i = 3; i <= tmp && i <= k && ans != 1; ++i) { if (n % i >= ans) continue; ans = min(ans, getsum(n, i)); } for (int l = tmp + 1, r; l <= k && ans != 1; l = r + 1) { r = min(n / (n / l), k); ans = min(ans, n / r + n % r); } printf("%d\n", ans); } return0; }
#include<bits/stdc++.h> usingnamespace std; using ll = longlong; int t; int n, k; int ans; inlineintgetsum(int n, int b){ int tot = 0; while (n) { tot += n % b; n /= b; } return tot; } intmain(){ freopen("base.in", "r", stdin); freopen("base.out", "w", stdout); scanf("%d", &t); while (t--) { scanf("%d%d", &n, &k); if (k == n) { puts("1"); continue; } ans = __builtin_popcount(n); if (k == n - 1) ans = min(ans, 2); for (int i = 3; i <= 1000 && i <= k && ans != 1; ++i) { ans = min(ans, getsum(n, i)); } for (int a = 0; a <= ans; ++a) { for (int b = 0; a + b <= ans; ++b) { for (int c = 0; a + b + c <= ans; ++c) { if (a + b == 0) continue; if (a + b + c >= n) break; if (a == 0) { if ((n - c) % b != 0) continue; int tmp = (n - c) / b; if (tmp > k || tmp <= a || tmp <= b || tmp <= c) continue; ans = min(ans, a + b + c); } else { ll delta = (ll)b * b - 4ll * a * (c - n); if (delta < 0) continue; ll sqr = sqrt(delta); if (sqr * sqr != delta) continue; delta = sqr; int x = -b + delta; if (x % (2 * a) != 0) continue; x = x / 2 / a; if (x > k || x <= min({a, b, c})) continue; ans = min(ans, a + b + c); } } } } printf("%d\n", ans); } return0; }