题面
略
题解
约瑟夫问题。编号~,每次拿第个。
:表示幸存的人的编号,
:优化:把若干连续的一起计算,直到加起来的值达到第一个模数,然后进行下一次。每次的时间与有关,所以总时间复杂度大概可能是的。
假设当前答案是,位置是,一起求的个数为,则:
移项就是
CODE
#include <bits/stdc++.h>
using namespace std;
int T, n, m;
int main () {
scanf("%d", &T); while(T--) {
scanf("%d%d", &n, &m);
if(m == 1) { printf("%d
", n); continue; }
int ans = 0;
for(int i = 1; i <= n && i <= m; ++i)
ans = (ans + m) % i;
for(int i = m+1, j; i <= n; i = j+1) {
j = min(i + (i-1-ans+m-2)/(m-1) - 1, n);
ans = (ans + 1ll*m*(j-i+1)) % j;
}
printf("%d
", ans+1); //题目中要求的编号是1~n,所以+1
}
}