请问各位，如何用更低的时间复杂度求使 $\sum_{i=1}^∞ \lfloor x \div a^i \rfloor \text{（代码中 $check$ 函数）}$ 值不小于 $n$ 的最小 $x$（$n$ 和 $a$ 已给出）。

已有算法的时间复杂度为： $O(log_2 (n \times a) \text{（注：二分法边界）} \times log_a(a \times n ) \text{（注：代码中 $check$ 函数）} )$

已有代码为：

//此处省略部分代码
long long check(int x, int a)
{
	long long tmp = a, ans = 0;
	while (tmp <= x)
	{
		ans += x / tmp;
		tmp *= a;
	}
	return ans;
}
//此处省略部分代码
long long l = 1, r = n * a;
while (l <= r)
{
	if (check(l + r >> 1, a) < n)
		l = (l + r >> 1) + 1;
	else
		r = (l + r >> 1) - 1;
}
cout << l;