「雅礼day4」嘟嘟噜 - 约瑟夫环

题目大意

多组询问求约瑟夫环问题答案。

---

题目分析

经典的约瑟夫环问题。
约瑟夫环有一种$O(n)$解法，若不会的推荐参考这里。

事实上我们观察一下该递推式。

$$f[i]=f[i-1]\times m\quad mod\,i$$

如果一个一个递推效率太慢，事实上我们发现某些时候在$f[i-1]\times m$后远远达不到$i$的级别，此时就不需要取模。
可以通过$\frac{i-sum-1}{m}$得到还需几次才会取模。
但是有可能在取模前游戏就结束了，所以说实际上这一次可以跳跃的次数为：$\min(n-i+1,\frac{i-sum-1}{m})$。

如果能够跳跃加速，就跳跃，否则就只进行一次以前的递推。

时间复杂度不清楚，$O($能过$)$。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
int t,n,m,sum=0;
int main() {
	t=Get_Int();
	while(t--) {
		n=Get_Int();
		m=Get_Int();
		sum=0;
		for(int i=2; i<=n; i++) {
			int k=min(n-i+1,(i-sum-1)/m);
			if(k>0) {
				sum+=k*m;
				i+=k-1;
			} else sum=(sum+m)%i;
		}
		printf("%d\n",sum+1);
	}
	return 0;
}