PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Srikkanth R and Daanish Mahajan
Tester: Miten Shah
Editorialist: Aman Dwivedi
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Maths, Observation
PROBLEM:
Let f(n, B) be the sum of digits of the integer n when written in base B.
More formally, if n = \sum\limits_{i=0}^{\infty} a_i B^i where a_i is an integer in the range [0, B-1], then f(n, B) = \sum\limits_{i=0}^{\infty} a_i.
Given Q queries, each consisting of two integers n and r. Find the value of B corresponding to which f(n, B) is minimum for all {\bf{2}} \leq B \leq r. If there are multiple such values, you can print any of them.
EXPLANATION:
In the previous version of the problem we have seen that we can solve the problem in O(\sqrt{N} *C) time complexity. But this complexity is not good enough to solve this version and hence we will get TLE.
The only thing that differs in the problem is constraints. Notice that l is fixed in this problem as 2, which gives us a hint that our final answer will be bounded by log(N). Since it only takes log(N) bits to represent any number in the binary system and hence, so our final answer will never exceed log(N).
As in this version, we know that our answer is bounded by log(N), we can fix the three least significant bits of the base B by using a log^3(N) loop and check whether aB^2+bB+c=N has some B which satisfy it.
This can be easily done by solving the quadratic expression and see if there is some B which satisfies the above equation and is less than r. Finally, we can take the minimum value of (a+b+c) over all the possible values of B which satisfies the equation.
This covers all the bases B whose value is greater than \sqrt[3]{N}, and then for the bases whose value is smaller than \sqrt[3]{N}, we can simply brute as we did in the previous version. Finally, we can output the base B which gives us the minimum possible digit sum (a+b+c) among all possible choices of B.
TIME COMPLEXITY:
O(\sqrt[3]{N} + log^3(N)) per query
SOLUTIONS:
Author's
#include <bits/stdc++.h>
#define LL long long
using namespace std;
clock_t start = clock();
LL readInt(LL l, LL r, char endd) {
LL x = 0;
char ch = getchar();
bool first = true, neg = false;
while (true) {
if (ch == endd) {
break;
} else if (ch == '-') {
assert(first);
neg = true;
} else if (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + ch - '0';
} else {
assert(false);
}
first = false;
ch = getchar();
}
if (neg) x = -x;
if (x < l || x > r) {
cerr << l << " " << r << " " << x << " failed\n";
}
assert(l <= x && x <= r);
return x;
}
string readString(int l, int r, char endd) {
string ret = "";
int cnt = 0;
while (true) {
char g = getchar();
assert (g != -1);
if (g == endd) {
break;
}
++cnt;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
LL readIntSp(LL l, LL r) {
return readInt(l, r, ' ');
}
LL readIntLn(LL l, LL r) {
return readInt(l, r, '\n');
}
string readStringSp(int l, int r) {
return readString(l, r, ' ');
}
string readStringLn(int l, int r) {
return readString(l, r, '\n');
}
void solve() {
LL n = readIntSp(2, (LL)1e12), r = readIntLn(2, (LL)1e12);
LL i, ret = -1, have = (LL)1e18;
auto update_base = [&](LL base) {
LL m = n, ans = 0;
while (m > 0) {
ans += m % base;
m /= base;
}
if (ans < have) {
have = ans;
ret = base;
}
};
update_base(2);
for (i=3;i*i*i<=n&&i<=r;++i) {
update_base(i);
}
LL lim = have;
cerr << ret << ' ';
for (LL a = 0; a <= lim; ++a) {
for (LL b = 0; b <= lim; ++b) {
for (LL C = 0; C <= lim; ++C) {
LL c = C - n;
if (a == 0) {
if (b == 0) {
continue;
}
LL base = -c / b;
if (base >= 2 && base <= r) {
update_base(base);
}
continue;
}
LL disc = b * b - 4 * a * c;
LL go = sqrtl(disc);
while (go * go < disc) ++go;
while (go * go > disc) --go;
if (go * go == disc) {
LL base = (go - b) / (2 * a);
if (base >= 2 && base <= r) {
update_base(base);
}
}
}
}
}
assert(ret >= 2 && ret <= r);
cout << ret << '\n';
}
int main() {
// Start solution here use readIntLn, readIntSp and readStringSp and readStringLn
// for reading input
int T = readIntLn(1, 300);
while (T--) {
solve();
}
// End solution here
assert(getchar() == EOF);
cerr << fixed << setprecision(10);
cerr << "Time taken = " << (clock() - start) / ((double)CLOCKS_PER_SEC) << " s\n";
return 0;
}
Tester
// created by mtnshh
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define rb pop_back
#define ti tuple<int, int, int>
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define mp make_pair
#define mt make_tuple
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repb(i,a,b) for(ll i=a;i>=b;i--)
#define err() cout<<"--------------------------"<<endl;
#define errA(A) for(auto i:A) cout<<i<<" ";cout<<endl;
#define err1(a) cout<<#a<<" "<<a<<endl
#define err2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<endl
#define err3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<endl
#define err4(a,b,c,d) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<" "<<#d<<" "<<d<<endl
#define all(A) A.begin(),A.end()
#define allr(A) A.rbegin(),A.rend()
#define ft first
#define sd second
#define V vector<ll>
#define S set<ll>
#define VV vector<V>
#define Vpll vector<pll>
#define endl "\n"
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
// char g = getc(fp);
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
// cerr << x << " " << l << " " << r << endl;
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
// char g=getc(fp);
assert(g != -1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
const ll max_q = 300;
const ll max_r = 1e12;
const ll max_n = 1e12;
const ll N = 200005;
const ll INF = 1e15;
ll solve(ll n, ll b){
ll sum = 0;
while(n){
sum += n % b;
n /= b;
}
return sum;
}
void solve(){
ll n = readIntSp(2, max_n), r = readIntLn(2, max_r);
ll mn = INF, ans = -1;
if(r >= n){
ans = n;
mn = 1;
}
ll x = solve(n, 2);
if(x < mn){
mn = x;
ans = 2;
}
for(ll i=2; i*i*i<=n; i++){
if(i>r) break;
ll x = solve(n, i);
if(x < mn){
mn = x;
ans = i;
}
}
ll y = mn;
rep(a,0,y) rep(b,0,y) rep(c,0,y){
if(a == 0){
if(b == 0){
continue;
}
ll B = (n - c) / b;
if(B < 2 or B > r) continue;
ll x = solve(n, B);
if(x < mn){
mn = x;
ans = B;
}
continue;
}
ll det = b*b - 4*a*(c-n);
ll det_sqrt = sqrt(det);
if(det_sqrt * det_sqrt < det){
det_sqrt += 1;
}
ll B = (det_sqrt - b) / (2 * a);
if(B < 2 or B > r) continue;
ll x = solve(n, B);
if(x < mn){
mn = x;
ans = B;
}
}
cout << ans << endl;
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll q = readIntLn(1, max_q);
while(q--){
solve();
}
assert(getchar()==-1);
}