最近在CF上补题，补到了一道关于约瑟夫环的题目（听都没听过，原谅我太菜）
就去好好学了一下，不过一般的题目应该是不会让你模拟过的，所以这次就做了一个约瑟夫环公式法变形的集合。
关于约瑟夫环的基础讲解，我个人认为最好的就是这篇了。
首先是最原始的约瑟夫环的题目：
https://vjudge.net/problem/51Nod-1073（小数据规模）
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m; int s = 0; cin >> n >> m; for (int i = 2; i <= n; i++) s = (s + m) % i; cout << s + 1 << endl; return 0; }
没啥好讲的直接套公式即可。
https://vjudge.net/problem/51Nod-1074（大数据规模）
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(0); cin.tie(0); ll n, m; ll ans = 0; cin >> n >> m; for (ll i = 2; i <= n; i++) { if (ans + m < i) { ll len = (i - ans) / m; if (len + i < n) { i += len; ans += m*len; } else { ans += m*(n-i); i = n; } } ans = (ans + m) % i; } cout << ans + 1 << endl; return 0; }
解题思路：
除去超大的n之外。就是个约瑟夫环的裸题。
约瑟夫环递推公式，n为人数，m为步长。
f(1) = 0
f(n) = [f(n-1)+m]%i i∈[2,n]
// f(n)还要经过起始位置修正，设起始位置为s，即ans=[f(n)+s]%n。
基本约瑟夫环优化就是当k=1的时候，每次递推就是在+1，可以直接算出来快速跳过，f(n)=f(1)+n-1
当n超大的时候，可以照着这种思路快速简化递推过程。在递推后期，f(x)+m在很长的周期内<i，假设有len个周期，
那么这些周期合并后的结果相当于f(x)+len*m。可以快速跳过。条件限制是: f(x)+len*m<i+(len-1)
可以推出来：
当len=1时，条件限制: f(x)+m<i
当len=2是，条件限制: f(x+1)+m<i+1=f(x)+2*m<i+1
当m=m时，条件限制：f(x)+len*m<i+(len-1)
化简有m<(i-f(x)-1)/(len-1)，若能整除，就是(i-f(x)-1)/(m-1)-1，否则就是(i-f(x)-1)/(m-1)直接取整。
这样，i+=len，f(x)+=m*len，快速跳过了中间过程。
若i+len>n，说明快速跳越界了，这时候可以直接算出f(n)=f(x)+(n-i-1)*len。
约瑟夫环变形问题一：
一圈共有N个人，开始报数，第i轮报到i的人自杀，然后重新开始报数，问最后自杀的人是谁？
思路：和原本的约瑟夫环问题的唯一区别是：m值不在固定。同样的我们将最后一位自杀者叫做p，那么在前一轮(第x轮)中的自杀者所报的号为x-1,第x轮中p的报号为x，如此下去……
得出公式：f(n) = (f(n-1) + n-(i-1)) % i，i∈[2,n] 其实我加粗的部分就是每一轮的步长(第一轮是1，第二轮是2···第六轮是6)，因为正过程是-，所以逆过程是+。
题目链接：https://vjudge.net/problem/HDU-5643
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while (t--) { int n; cin >> n; int ans = 0; for (int i = 2; i <= n; i++) { ans = (ans + n - (i-1)) % i; } cout << ans + 1 << endl; } return 0; }
原文：https://www.cnblogs.com/Vikyanite/p/12236482.html
