11025번: 조세퍼스 문제 3

https://www.acmicpc.net/problem/11025


$O(n)$

조세퍼스 수열의 점화식은 (n,m) = ((n-1,m)+m-1)%n+1 이다. (1부터 시작)
이것을 유도하는 것은 크게 어렵지 않으니 생각해보고 정 모르겠으면 wiki를 참고하자.

#include<stdio.h>
int n, m, r = 1;
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 2; i <= n; i++) r = (r + m - 1) % i + 1;
    printf("%d", r);
    return 0;
}