题解 ABC293F【Zero or One】

我们可以暴力检查进制数不超过 \(B\) 的是否符合要求；然后对于进制数大于 \(B\) 的，位数不超过 \(\log_BN\)，可以暴力枚举每一位的值然后二分进制数检查。

代码中 \(B=10^3\)。

// Problem: F - Zero or One
// Contest: AtCoder - AtCoder Beginner Contest 293
// URL: https://atcoder.jp/contests/abc293/tasks/abc293_f
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(ll x=(y);x<=(z);x++)
#define per(x,y,z) for(ll x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
#define likely(exp) __builtin_expect(!!(exp), 1)
#define unlikely(exp) __builtin_expect(!!(exp), 0)
using namespace std;
typedef long long ll;

mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
ll randint(ll L, ll R) {
	uniform_int_distribution<ll> dist(L, R);
	return dist(rnd);
}

template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

ll T, n;

ll cmp(ll n, ll S, ll B) {
	__int128 val = 0;
	rep(i, 0, 5) {
		val = val * B + ((S >> i) & 1);
		if(val > n) return 1;
	}
	return val < n ? -1 : 0;
}

int main() {
	for(scanf("%lld", &T); T; T--) {
		scanf("%lld", &n);
		ll ans = 0;
		rep(B, 2, 1000) {
			bool ok = true;
			for(ll i = n; i; i /= B) ok &= i % B <= 1;
			ans += ok;
		}
		rep(i, 1, 63) {
			ll L = 1001, R = n; bool ok = false;
			while(L <= R) {
				ll M = (L + R) >> 1, qwq = cmp(n, i, M);
				if(!qwq) {ok = M > 1000; break;}
				if(qwq == -1) L = M + 1;
				else R = M - 1;
			}
			ans += ok;
		}
		printf("%lld\n", ans);
	}
	return 0;
}