Problem:
 Score : 100 points    Problem Statement You are given an integer N . Consider an infinite N -ary tree as shown below:    Figure: an infinite N -ary tree for the case N = 3   As shown in the figure, each vertex is indexed with a unique positive integer, and for every positive integer there is a vertex indexed with it. The root of the tree has the index 1 . For the remaining vertices, vertices in the upper row have smaller indices than those in the lower row. Among the vertices in the same row, a vertex that is more to the left has a smaller index.  Regarding this tree, process Q queries. The i -th query is as follows:   Find the index of the lowest common ancestor (see Notes) of Vertex v_i and w_i .       Notes  In a rooted tree, the lowest common ancestor (LCA) of Vertex v and w is the farthest vertex from the root that is an ancestor of both Vertex v and w . Here, a vertex is considered to be an ancestor of itself. For example, in the tree shown in Problem Statement, the LCA of Vertex 5 and 7 is Vertex 2 , the LCA of Vertex 8 and 11 is Vertex 1 , and the LCA of Vertex 3 and 9 is Vertex 3 .       Constraints  1 ≤ N ≤ 10^9  1 ≤ Q ≤ 10^5  1 ≤ v_i < w_i ≤ 10^9         Input Input is given from Standard Input in the following format:  N  Q  v_1  w_1  :  v_Q  w_Q       Output Print Q lines. The i -th line (1 ≤ i ≤ Q) must contain the index of the lowest common ancestor of Vertex v_i and w_i .        Sample Input 1 3 3
5 7
8 11
3 9      Sample Output 1 2
1
3  The queries in this case correspond to the examples shown in Notes.       Sample Input 2 100000 2
1 2
3 4      Sample Output 2 1
1

Solution (Python):




import sys
readline = sys.stdin.readline

N,Q = map(int,readline().split())

for i in range(Q):
  v,w = map(int,readline().split())
  if N == 1:
    print(min(v,w))
    continue
  v -= 1
  w -= 1
  while v != w:
    if v > w:
      v = (v - 1) // N
    else:
      w = (w - 1) // N
  print(v + 1)

Solution (Python):
import sys
input = sys.stdin.readline
N,Q = map(int,input().split())
VW = [tuple(map(int,input().split())) for i in range(Q)]

ans = []
if N==1:
    for v,w in VW:
        ans.append(min(v,w))
else:
    for v,w in VW:
        while v != w:
            if v > w: v,w = w,v
            w = (w+N-2)//N
        ans.append(v)
print(*ans, sep='\n')

Solution (Python):
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N, Q = map(int, input().split())

if N == 1:
    ans = [min(map(int, input().split())) for _ in range(Q)]
    print(*ans, sep="\n")
    exit()

ans = [-1] * Q
for i in range(Q):
    x, y = map(int, input().split())
    x_memo = [x]
    y_memo = [y]
    while x:
        x = (x + N - 2) // N
        x_memo.append(x)
    while y:
        y = (y + N - 2) // N
        y_memo.append(y)

    res = -1
    while x_memo and y_memo:
        xi = x_memo.pop()
        yi = y_memo.pop()
        if xi == yi:
            res = xi
        else:
            break
    ans[i] = res

print(*ans, sep="\n")

Solution (Python):
N,Q=map(int,input().split())
if N>1:
    def find_par(x):
        u=x%N-1
        if u<=0:
            u+=N
        return (x-u-1)//N+1
    def path(x):
        s_node=x
        d=[s_node]
        while s_node!=1:
            s_node=find_par(s_node)
            d.append(s_node)
        return d
    for _ in range(Q):
        v,w=map(int,input().split())
        data1=set(path(v))
        data2=set(path(w))
        print(max(data1 & data2))
else:
    for _ in range(Q):
        v,w=map(int,input().split())
        print(min(v,w))

Solution (Python):
import sys
input=sys.stdin.readline
n,q=map(int,input().split())
for i in range(q):
    u,v=map(int,input().split())
    if n==1:
        print(min(u,v))
        continue
    u-=1
    v-=1
    while u!=v:
        if u>v:
            if (u-1)//n>v:
                u=(((u-1)//n)-1)//n
            else:
                u=(u-1)//n
        else:
            if (v-1)//n>v:
                v=(((v-1)//n)-1)//n
            else:
                v=(v-1)//n
    print(u+1)

Solution (Python):
def main():
    n,m=map(int,input().split())
    ab=[list(map(int,input().split())) for _ in [0]*m]
    if n==1:
        for a,b in ab:
            print(min(a,b))
        return
    for a,b in ab:
        while a!=b:
            if a<b:
                b=(b+n-2)//n
            else:
                a=(a+n-2)//n
        print(a)
    
main()

Solution (Python):
def main():
    n,m=map(int,input().split())
    ab=[list(map(int,input().split())) for _ in [0]*m]
    if n==1:
        for a,b in ab:
            print(min(a,b))
        return
    for a,b in ab:
        while a!=b:
            a,b=min(a,b),max(a,b)
            b=(b+n-2)//n
        print(a)
    
main()

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

ans = ""
n, q = [int(item) for item in input().split()]
if n == 1:
    for i in range(q):
        v, w = [int(item) for item in input().split()]
        print(min(v, w))
    exit()

for i in range(q):
    v, w = [int(item) - 1 for item in input().split()]
    while v != w:
        if v > w:
            v = (v - 1) // n
        else:
            w = (w - 1) // n
    print(v + 1)

Solution (Python):
n,q=map(int,input().split())
if n==1:
    for i in range(q):
        v,w=map(int,input().split())
        print(min(v,w))
else:
    for i in range(q):
        v,w=map(int,input().split())
        while v!=w:
            if v>w:v,w=w,v
            w=(w+n-2)//n
        print(v)

Solution (Python):
import sys
def main():
    def input():
        return sys.stdin.readline()[:-1]
    N, Q = map(int,input().split())
    ans = []
    if N == 1:
        for k in range(Q):
            v, w = map(int,input().split())
            ans.append(min(v,w))
    else:
        for k in range(Q):
            v, w = map(int,input().split())
            while v!=w:
                if v > w:
                    v, w = w, v
                w = (w+N-2)//N
            ans.append(v)
    print(*ans,sep="\n")

if __name__ == '__main__':
    main()

Solution (Python):
import bisect
n, q = [ int(v) for v in input().split() ]

if n != 1:
    tree_list = [0] + [ (n**(i+1)-1) // (n-1) for i in range(100) if (n**(i+1)-1) // (n-1) <= 10**9 ]

def upward(a):
    d = bisect.bisect_left(tree_list,a) - 1
    outlist = []
    for i in range(d+1):
        outlist.append(a)
        if i < d:
            a -= tree_list[d-i] + 1
            a //= n
            a += tree_list[d-i-1] + 1
    return d, outlist

def lca(a,b):
    da, a_list = upward(a)
    db, b_list = upward(b)

    if da < db:
        da, db = db, da
        a_list, b_list = b_list, a_list
    s = da - db
    ans = None
    for i in range(db+1):
        if a_list[s+i] == b_list[i]:
            ans = a_list[s+i]
            break
    return ans



for i in range(q):
    v, w = [ int(v) for v in input().split() ]
    if n != 1:
        print(lca(v,w))
    else:
        print(min(v,w))

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007


n, q = LI()




for i, j in LIR(q):
    if n == 1:
        print(min(i, j))
    else:
        while i != j:
            if i < j:
                i, j = j, i
            i = (i - 2) // n + 1
        print(i)

Solution (Python):
N, Q = map(int, input().split())
queries = []
for i in range(Q):
    v, w = map(int, input().split())
    queries.append([v, w])

if N == 1:
    for v, w in queries:
        print(min(v, w))
else:
    for v, w in queries:
        if 1 in [v, w]:
            print(1)
        else:
            
            v, w = min(v,w), max(v, w)
            v -= 2
            w -= 2
            v_parents = [v]
            isReported = False
            while v > 0:
                v_parents.append(v // N - 1)
                v = v//N-1
            while w > 0:
                w = w // N-1
                if w in v_parents:
                    print(w+2)
                    isReported = True
                    break
            if not isReported:
                print(1)

Solution (Python):
import math
N, Q = map(int, input().split())
queries = []
for i in range(Q):
    v, w = map(int, input().split())
    queries.append([v, w])

if N == 1:
    for v, w in queries:
        print(min(v, w))
else:
    for v, w in queries:
        if 1 in [v, w]:
            print(1)
        else:
            
            v, w = min(v,w), max(v, w)
            v -= 2
            w -= 2
            v_parents = [v]
            isReported = False
            while v > 0:
                v_parents.append(v // N - 1)
                v = v//N-1
            while w > 0:
                w = w // N-1
                if w in v_parents:
                    print(w+2)
                    isReported = True
                    break
            if not isReported:
                print(1)

Solution (Python):
n,q = map(int, input().split())
if n == 1:
  for _ in range(q):
    print(min(map(int, input().split())))
else:
  for _ in range(q):
    v,w = map(int, input().split())
    while v != w:
      if v > w:
        v,w = w,v
      w = (w+n-2)//n
    print(v)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

N,Q = map(int,input().split())
V,W = np.array([input().split() for _ in range(Q)],dtype=np.int64).T

if N == 1:
    answer = np.minimum(V,W)
else:
    for _ in range(50):
        V[V>W] = (V[V>W]+N-2)//N
        W[W>V] = (W[W>V]+N-2)//N
    answer = V

print('\n'.join(answer.astype(str)))

Solution (Python):
n,q,*t=map(int,open(0).read().split())
for v,w in zip(t[::2],t[1::2]):
 while n>1and v!=w:
  if v>w:v,w=w,v
  w=(w+n-2)//n
 print(v)

Solution (Python):
n,q,*t=map(int,open(0).read().split())
for v,w in zip(t[::2],t[1::2]):
 if~-n:
  while v!=w:
   if v>w:v,w=w,v
   w=(w+n-2)//n
 print(v)

Solution (Python):
n,q,*t=map(int,open(0).read().split())
for v,w in zip(t[::2],t[1::2]):
  if n-1:
    while v!=w:
      if v>w:v,w=w,v
      w=(w+n-2)//n
  print(v)

Solution (Python):
n,q,*t=map(int,open(0).read().split())
for v,w in zip(t[::2],t[1::2]):
  while n>1and v!=w:
    if v>w:v,w=w,v
    w=(w+n-2)//n
  print(v)

Solution (Python):
def main():
  n,q,*t=map(int,open(0).read().split())
  for v,w in zip(t[::2],t[1::2]):
    if n<2:
      print(min(v,w))
      continue
    s,t=[],[]
    while v:
      s.append(v)
      v=(v+n-2)//n
    while w:
      t.append(w)
      w=(w+n-2)//n
    print(max(set(s)&set(t)))
if __name__=='__main__':
  main()

Solution (Python):
n,q,*t=map(int,open(0).read().split())
for v,w in zip(t[::2],t[1::2]):
  if n<2:
    print(min(v,w))
    continue
  s,t=set(),set()
  while v:
    s|={v}
    v=(v+n-2)//n
  while w:
    t|={w}
    w=(w+n-2)//n
  print(max(s&t))

Solution (Python):
N, Q = map(int, input().split())
vws = [tuple(map(int, input().split())) for _ in range(Q)]

anss = []
if N == 1:
    anss = [min(v, w) for v, w in vws]
else:
    for v, w in vws:
        v, w = v-1, w-1
        while v != w:
            if v > w:
                v = (v-1)//N
            else:
                w = (w-1)//N
        anss.append(v + 1)

print('\n'.join(map(str, anss)))

Solution (Python):
N, Q = map(int, input().split())
if N == 1:
    for _ in range(Q):
        v, w = map(int, input().split())
        print(min(v, w))
else:
    L = [1]
    aa = 1
    def ch(k):
        return (k-2)//N+1
    
    def chh(a, b):
        if a == b:
            return a
        
        if a > b:
            a, b = b, a
        
        return chh(a, ch(b))
        
    for _ in range(Q):
        v, w = map(int, input().split())
        print(chh(v, w))

Solution (Python):
import sys
N, Q = map(int, input().split())
query = []
for i in range(Q):
    v, w = map(int, input().split())
    if v < w:
        v, w = w, v
    query.append((v - 1, w - 1))


def f(v, w):
    L = set()
    L.add(0)
    while w != 0:
        L.add(w)
        w = (w - 1) // N
    while v != 0:
        if v in L:
            return v + 1
        v = (v - 1) // N
    return 1

if N==1:
    for v, w in query:
        print(w+1)
    sys.exit()
for v, w in query:
    print(f(v, w))

Solution (Python):
N,Q = map(int,input().split())
if N == 1:
    for i in range(Q):
        print(min(map(int,input().split())))
    exit()

def solve(s):
    a,b = map(int,s.split())
    while a != b:
        if a < b: a,b = b,a
        a = (a+N-2) // N
    return str(a)

print('\n'.join(map(solve, [input() for i in range(Q)])))

Solution (Python):
n, q = map(int, input().split())

if n == 1:
    def solve(v, w):
        return min(v, w)
else:
    def solve(v, w):
        while v != w:
            if v > w:
                v, w = w, v
            w = (w + n - 2) // n
        return v

print('\n'.join(map(str, (solve(*map(int, input().split())) for _ in range(q)))))

Solution (Python):
N, Q = map(int, input().split())

if N == 1:
    for i in range(Q):
        V, W = map(int, input().split())
        print(min(V, W))
else:
    p = []
    p.append(1)
    for i in range(40):
        p.append(p[-1] * N)

    for i in range(Q):
        V, W = map(int, input().split())

        v = []
        w = []
        dv = 0
        dw = 0

        while V > (p[dv + 1] - 1) // (N - 1): dv = dv + 1
        while W > (p[dw + 1] - 1) // (N - 1): dw = dw + 1

        v.append(V)
        e = V
        for j in range(dv, 0, -1):
            e = (e - (p[j] - 1) // (N - 1) - 1) // N + (p[j - 1] - 1) // (N - 1) + 1;
            v.append(e)
        v.reverse()

        w.append(W)
        e = W
        for j in range(dw, 0, -1):
            e = (e - (p[j] - 1) // (N - 1) - 1) // N + (p[j - 1] - 1) // (N - 1) + 1;
            w.append(e)
        w.reverse()

        ans = 1
        j = 0
        while j < len(v) and j < len(w) and v[j] == w[j]:
            ans = v[j]
            j = j + 1
        print(ans)

Solution (Python):
from bisect import *
N, Q = map(int, input().split())
ans = []
if N == 1:
    for q in range(Q):
        v, w = map(int, input().split())
        print(v)
else:
    c = 1
    B = [1]
    while c < 10**9:
        B.append(c+1)
        c = c*N + 1
    for q in range(Q):
        v, w = map(int, input().split())
        for i in range(bisect(B, v), bisect(B, w)):
            w = (w + (N - 2)) // N
        while v != w:
            v = (v + (N - 2)) // N
            w = (w + (N - 2)) // N
        print(v)

Solution (Python):
from bisect import *
from sys import stdin, stdout
readline = stdin.readline
N, Q = map(int, readline().split())
ans = []
if N == 1:
    for q in range(Q):
        v, w = map(int, readline().split())
        ans.append(str(v))
else:
    c = 1
    B = [1]
    while c < 10**9:
        B.append(c+1)
        c = c*N + 1
    for q in range(Q):
        v, w = map(int, readline().split())
        lv = bisect(B, v)
        lw = bisect(B, w)
        if lv < lw:
            w = (w + (B[lw-lv]-1)*(N-2)) // N**(lw-lv)
        while v != w:
            v = (v + (N - 2)) // N
            w = (w + (N - 2)) // N
        ans.append(str(v))
stdout.write("\n".join(ans))
stdout.write("\n")

Solution (Python):
N, Q = map(int, input().split())

if N == 1:
    for i in range(Q):
        V, W = map(int, input().split())
        print(min(V, W))
else:
    p = []
    p.append(1)
    for i in range(40):
        p.append(p[-1] * N)

    for i in range(Q):
        V, W = map(int, input().split())

        v = []
        w = []
        dv = 0
        dw = 0

        while V > (p[dv + 1] - 1) // (N - 1): dv = dv + 1
        while W > (p[dw + 1] - 1) // (N - 1): dw = dw + 1

        v.append(V)
        e = V
        for j in range(dv, 0, -1):
            e = (e - (p[j] - 1) // (N - 1) - 1) // N + (p[j - 1] - 1) // (N - 1) + 1;
            v.append(e)
        v.reverse()

        w.append(W)
        e = W
        for j in range(dw, 0, -1):
            e = (e - (p[j] - 1) // (N - 1) - 1) // N + (p[j - 1] - 1) // (N - 1) + 1;
            w.append(e)
        w.reverse()

        ans = 1
        j = 0
        while j < len(v) and j < len(w) and v[j] == w[j]:
            ans = v[j]
            j = j + 1
        print(ans)