Submission #39648391

---

Source Code Expand

// हर हर महादेव
using namespace std;
#include <bits/stdc++.h>
#define int long long int

const int lim = 1e3 + 5;
const int dig = 7;
const int N = (int) 1e18 + 50;
const int inf = (int) 1e18 + 50;

bool check(int n,int b){
	while(n){
		if(abs(n % b) > 1){
			return false;
		}
		n /= b;
	}
	return true;
}

int interpret_in_base_b(int mask,int b){
	int ans = 0;
	__int128 pw = 1;
	bool flag = false;
	for(int i = 0; i < dig; i++){
		if(1 << i & mask){
			if(flag){
				return inf;
			}
			ans += pw;
		}
		pw *= b;
		if(pw > N){
			flag = true;
		}
	}
	return ans;
}

int binary_search_base(int n,int mask){ // value of b for which mask interpreted in base b is equal to n. Returns -1 if there is no such b
	int l = 0,r = N,ans = -1;
	while(l <= r){
		int m = (l + r) >> 1;
		if(interpret_in_base_b(mask,m) <= n){
			ans = m;
			l = m + 1;
		}
		else{
			r = m - 1;
		}
	}
	
	return interpret_in_base_b(mask,ans) == n ? ans : -1;
}

void testcase(){
	
	int n; cin >> n;
	
	// checking for b in [2,1000)
	int ans = 0;
	for(int i = 2; i < lim; i++){
		ans += check(n,i);
	}
	
	
	// bitmasking + binary search
	for(int mask = 1;mask < (1 << dig);mask++){
		int here = binary_search_base(n,mask);
		if(here >= lim){
			ans++;
		}
	}
	cout << ans << '\n';
}

int32_t main(){
	ios::sync_with_stdio(false);cin.tie(0);
	
	int tt; cin >> tt;
	
	while(tt--){
		testcase();
	}
	return 0;
}

Submission Info

Judge Result