잘못 작성한 요세푸스 코드

시간 제한2초메모리 제한128 MB

요약

n, k가 최대 10억일 때 i=1부터 n까지 k mod i의 합을 약수 구간 분할 기법으로 빠르게 계산합니다.

문제

요세푸스 문제의 답을 다음 의사 코드로 구할 수 있다고 하자.

r := 0
for i from 1 to n do
    r := (r + k) mod i
return r

어떤 프로그래머가 이 코드를 잘못 읽고 다음과 같이 작성했다.

r := 0
for i from 1 to n do
    r := r + (k mod i)
return r

n과 k가 주어졌을 때, 잘못 작성된 코드가 반환하는 값을 출력하는 프로그램을 작성하시오.

첫째 줄에 정수 n과 k가 주어진다. (1 <= n, k <= 10^9)

첫째 줄에 잘못 작성된 코드가 반환하는 값을 출력한다.