Джозефус для больших n (Facebook Hacker Cup)

На прошлой неделе я участвовал в 1b раунде Facebook Hacker cup.

Одна из задач проблемы были в основном проблемой Иосифа

I ' Раньше я изучал проблему Иосифа как дискретную математическую задачу, поэтому я в основном понимаю, как получить повторение:

f(n,k) = (f(n-1,k) + k) mod n, with f(1,k) = 0

Но это не сработало в Facebook Hacker Cup, потому что максимальное значение n было 10 ^ 12. Значение mak для k было 10 ^ 4.

Википедия упоминает подход, когда k мало, а n большое. В основном удаляйте людей из одного раунда, а затем меняйте нумерацию. Но это мало описано, и я не понимаю, почему работает перенумерация.

Я просмотрел образец рабочего исходного кода для решения, но я все еще не понимаю эту последнюю часть.

long long joseph (long long n,long long k) {
    if (n==1LL) return 0LL;
    if (k==1LL) return n-1LL;
    if (k>n) return (joseph(n-1LL,k)+k)%n;
    long long cnt=n/k;
    long long res=joseph(n-cnt,k);
    res-=n%k;
    if (res<0LL) res+=n;
    else res+=res/(k-1LL);
    return res;
}

Часть, которую я действительно не знаю » t Понять начинается с res- = n% k (и строк после него). Как вы пришли к выводу, что это способ корректировки результата?

Может ли кто-нибудь показать обоснование того, как это получается? Или ссылку, по которой это происходит? (Я не нашел никакой информации на форумах UVA или топкодеров)