Consider the infinite x$x$ axis. There are N$N$ impacts on this X-axis at integral points (X1$X_1$,X2$X_2$,....XN$X_N$)  (all distinct) . An impact at a point X$X$i propagates such that at a point X$X$0, the effect of the impact is K|Xi−X0|$K^{|X_i - X_0|}$. Given the point X0$X_0$, N$N$ and K$K$. Assume the total impact on X0$X_0$ is M$M$, find if it is possible to do so.Note: You are not required to find the set X

Formally print "yes" if this is possible and "no" if not possible.

-----Input:-----
- First line will contain T$T$, number of testcases. Then the testcases follow. 
-  Each testcase contains of a single line of input, four integers N$N$,K$K$,M$M$,X$X$0 

-----Output:-----
-  The output of each test case is either "yes" or "no"

-----Constraints -----
-  1≤T≤1000$1\leq T \leq 1000$
-  1≤N≤100$1\leq N \leq 100$
-  1≤K≤1000$1\leq K \leq 1000$
-  1≤M≤1018$1\leq M \leq 10^{18}$
-  −109≤X0≤109$-10^9 \leq X_0 \leq 10^9$ 

-----Sample Input:-----
	2

4 3 10 10

2 3 10 10

-----Sample Output:-----
	no

yes

Source: codechef | Difficulty: VERY_HARD
Tags: Constructive algorithms

Implementation

Ad-hoc


Solutions:
T = int(input())
for i in range(T):
	l = list(map(int, input().split()))
	(n, k, m, x) = (l[0], l[1], l[2], l[3])
	if k == 1:
		if n == m:
			print('yes')
		else:
			print('no')
	elif m % k > 1:
		print('no')
	elif k == 2:
		stack = []
		var = 0
		while m != 0:
			var += m % k
			stack.append(m % k)
			m //= k
		if var > n:
			print('no')
		elif var == n:
			print('yes')
		else:
			for p in range(100):
				for q in range(2, len(stack)):
					if stack[q - 1] == 0 and stack[q] >= 1:
						stack[q - 1] = 2
						stack[q] -= 1
						var += 1
						if var == n:
							print('yes')
			if var < n:
				print('no')
	else:
		temp = 0
		rog = 1
		while m != 0:
			if m % k > 2:
				rog = 0
				print('no')
			temp += m % k
			m //= k
		if rog:
			if temp == n:
				print('yes')
			else:
				print('no')


from math import log
try:
	for i in range(int(input())):
		a = input().split(' ')
		(n, k, x, m) = map(int, a)
		ans = 'no'
		u = 0
		if k != 2 and k != 1:
			if x % k == 0:
				x //= k
				u = -1
			elif x % k == 1:
				n -= 1
				x //= k
				u = -1
			if u == -1:
				while x != 0:
					if x % k == 0:
						x //= k
					elif x % k == 1:
						x //= k
						n -= 1
					elif x % k == 2:
						x //= k
						n -= 2
					else:
						break
			if n == 0 and x == 0:
				ans = 'yes'
		elif k == 1:
			if x == n:
				ans = 'yes'
		else:
			lst = []
			p = 0
			N = n
			while x != 0:
				if x % 2 == 0:
					x //= 2
					p += 1
				elif x % 2 == 1:
					x //= 2
					n -= 1
					p += 1
					lst.append(2 ** (p - 1))
			if len(lst) == N:
				ans = 'yes'
			if len(lst) < N:
				k = 0
				g = len(lst)
				if lst[0] > 2:
					g += int(log(lst[0]) // log(2)) - 1
					k = 1
				for i in range(1, len(lst)):
					if k == 1:
						g += int(log(lst[i] // lst[i - 1], 2))
					elif lst[i] > 2 * lst[i - 1]:
						g += int(log(lst[i] // lst[i - 1], 2)) - 1
						k = 1
					else:
						k = 0
				if g >= N:
					ans = 'yes'
		print(ans)
except EOFError as e:
	pass