Problem:


監獄

無限人の囚人たちがいる。はじめ、囚人たちは 0, 1, 2, ... と番号が振られている。

次の操作を N 回行う。

0 番目の囚人を釈放し、k, 2k, 3k, ... 番目の囚人たちを処刑する。

その後、残った囚人たちに番号を振り直す。このとき、元の番号が小さい囚人から順に 0, 1, 2,  ... と番号を振る。

N 回目の操作で釈放される囚人がはじめに振られていた番号を求めよ。

Constraints

1 ≤ N ≤ 10^5

2 ≤ k  ≤ 10^5

答えは 10^{18} 以下である。

Input Format

入力は以下の形式で標準入力から与えられる。

N k

Output Format

答えを一行に出力せよ。

Sample Input 1

4 2

Sample Output 1

7

Sample Input 2

1 3

Sample Output 2

0

Sample Input 3

100000 100000

Sample Output 3

99999



Sample input:
4 2


Sample output:
7

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Here your code !




def main(N,k):
    p = 0
    for i in range(N-1):
        p2 = p
        while p2-1-p2//k != p:
            p2+=1
        p=p2
    return p




if __name__ == '__main__':
    N,k=input().split()
    print(main(int(N),int(k)))

Submission status: Accepted

Solution code:
# coding: utf-8
# Here your code !

def main(N,k):
    p = 0
    p2 = 0
    memo = 0
    for i in range(N-1):
        p, p2 = p2, k*(p2+1)//(k-1) - 2
        while p2-1-p2//k != p:
            p2+=1
    return p2

if __name__ == '__main__':
    N,k=input().split()
    print(main(int(N),int(k)))

Submission status: Accepted

Solution code:
n, k = map(int, raw_input().split())
left = 0; right = 10**18+1
while left+1<right:
    mid = (left + right) / 2
    c = mid
    for i in xrange(n-1):
        c -= (c+k-1)/k
    if c < 1:
        left = mid
    else:
        right = mid
print left

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=0
for _ in range(n-1):a+=a//(k-1)+1
print(a)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n, k = map(int, input().split())
a = 0
for i in range(n-1):
    a = a * k // (k - 1) + 1
print(a)

Submission status: Accepted

Solution code:
b, k = map(int, raw_input().split())
g=0
for i in range(0,b-1):
	g=1+(k*g)/(k-1)
print g

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,k = LI()

    t = 0
    for _ in range(n-1):
        t = t * k // (k-1) + 1
    return t



print(main())

Submission status: Accepted

Solution code:
# def test(k):
#     res = [0]*20
#     l = [i for i in range(20)]
#     t = 1
#     while l:
#         i = 0
#         while i < len(l):
#             res[l.pop(i)] = t
#             i += k-1
#         t += 1
#     return res
# for k in range(2,11):
#     print(k,":",test(k))

from math import floor

N, k = map(int, input().split())
l, r = -1, 10**18
while l+1 < r:
    m = (l+r) >> 1
    x = m
    for i in range(1, N):
        x -= x // k + 1
    if 0 <= x:
        r = m
    else:
        l = m
print(r)

Submission status: Accepted

Solution code:
n, k = map(int,input().split())

now = 0

while n > 1:
    n -= 1
    now = (now * k) // (k - 1) + 1

print(now)

Submission status: Accepted

Solution code:
N,K = map(int, input().split())
ans = 1
for _ in range(N-1):
    ans += (ans+K-2)//(K-1)
print(ans-1)

Submission status: Accepted

Solution code:
N, k = [int(i) for i in input().split()]
ans = 0
for i in range(N - 1):
  ans = (ans * k + k - 1) // (k - 1)
print(ans)

Submission status: Accepted

Solution code:
def horizontal_input(T=str):
    return list(map(T,input().split()))

def vertical_input(n,T=str,sep=False,septype=tuple):
    data=[]
    if sep:
        for i in range(n):
            data.append(septype(map(T,input().split())))
    else:
        for i in range(n):
            data.append(T(input()))
    return data

n,k=horizontal_input(int)
prisoner=0
for i in range(n-1):
    prisoner+=1
    prisoner+=(prisoner-1)//(k-1)
print(prisoner)