Incorrect Josephus Code
Time limit2sMemory limit128 MB
Given n and k up to 1e9, compute the sum of k mod i for i from 1 to n efficiently using divisor block decomposition.
- Level
Medium6 of 10
- Topics
- Number theory, Math, Two pointers
- Solved
- No attempts yet
Problem
Suppose the Josephus problem can be solved by the following pseudocode.
r := 0
for i from 1 to n do
r := (r + k) mod i
return r
A programmer misread the code and wrote it as follows instead.
r := 0
for i from 1 to n do
r := r + (k mod i)
return r
Given n and k, write a program that prints the value returned by the incorrect code.
Input
The first line contains two integers n and k. (1 <= n, k <= 10^9)
Output
Print the value returned by the incorrect code.