题干：
N个人坐成一个圆环（编号为1 - N），从第1个人开始报数，数到K的人出列，后面的人重新从1开始报数。问最后剩下的人的编号。
例如：N = 3，K = 2。2号先出列，然后是1号，最后剩下的是3号。
Input
2个数N和K，表示N个人，数到K出列。(2 <= N, K <= 10^6)
Output
最后剩下的人的编号
Input示例
3 2
Output示例
3
解题报告：
思路: 直接模拟的话O(n*k)的时间复杂度,按照套路来的话这样的题一般是能找规律的; 我们先将n个人的编号改成0~n-1(别问为什么,套路而已),那么第1次报到号码为k-1的人出列,圈里还剩下n-1个人 我们对比一下出列前后的编号: 出列前: 0, 1, 2, 3, 4, 5, 6, ...k-2, k-1, k... n-1 出列后: n-k+1,..................n-2, , 1... n-k 我们可以发现留下的人编号和留下来之前是一一对应的,那么要是能找到对应关系的话问题就迎刃而解了,不过现在数据太多了不好找 (偶就是这里找错了规律然后只过了样例),我们接着往下想想... 按照前面的规律,第n次报数时只有一个人,我们给他重新编号为0.前面我们也知道了某一轮某个人的编号和上一轮是对应的,最后留下的人此时的编号为0, 那么只要我们由它上溯并找到它在第一轮时的编号答案就出来了啦~ 我们用f(x)表示最后留下来那个人在第n-x+1轮中的编号(这样做我们就是由f(1)推f(n),更直观一些,反之由f(n)推f(1)也是可以的),那么f(n)+1就是 最终答案了啦.很显然有f(1)=0(因为此时只剩下一个人了嘛),接下来我们需要找到两轮编号之间的映射关系,这个可以有枚举k和x得到,这里就不写枚举 过程了啦~ 最后我们可以得到公式 f(x)=(f(x-1)+k)%x;
AC代码：
#include <bits/stdc++.h>
using namespace std;
int main(void){
int gg, n, k;
cin >> n >> k;
gg=0;
for(int i=2; i<=n; i++){
gg=(gg+k)%i; //前面说的f(x)只是为了我们更直观地理解,其实直接用一个变量保存上一轮序号就可以了
}
cout << gg+1 << endl;
return 0;
} 
京公网安备 11010502036488号