Given two numbers a and b, we have to find the nth number which is divisible by a or b.
The format looks like below:
Input: First line consists of an integer T, denoting the number of test cases. Second line contains three integers a, b and N
Output: For each test case, print the Nth number in a new line.
Constraints:
1≤t≤105
1≤a,b≤104
1≤N≤10
Sample Input
1 2 3 10
Sample Output
15
Explanation
The numbers which are divisible by 2 or 3 are: 2,3,4,6,8,9,10,12,14,15 and the 10th number is 15.
For single test case input 2000 3000 100000 it is taking more than one second to complete. I want to know if I can get the results in less than 1 second. Is there a time efficient approach to this problem, maybe if we can use some data structure and algorithms here?
test_case=input()
if int(test_case)<=100000 and int(test_case)>=1:
for p in range(int(test_case)):
count=1
j=1
inp=list(map(int,input().strip('').split()))
if inp[0]<=10000 and inp[0]>=1 and inp[1]<=10000 and inp[1]>=1 and inp[1]<=1000000000 and inp[1]>=1:
while(True ):
if count<=inp[2] :
k=j
if j%inp[0]==0 or j%inp[1] ==0:
count=count+1
j=j+1
else :
j=j+1
else:
break
print(k)
else:
break
Is there a time efficient…[use of]…algorithm
sort of - this asks for math. \$\endgroup\$