#include<cstdio> #include<algorithm> using namespace std; typedef long long LL; LL solve(LL n,LL m,LL s) { if(m==1) return (n-1+s)%n; LL ans=0,i=2; while(i<=n) { if(ans+m<i)///递增时,x为增加次数 { LL x=(i-ans-1)%(m-1)?(i-ans-1)/(m-1):(i-ans-1)/(m-1)-1; if(i+x>n) { ans+=(n+1-i)*m; break; } i+=x; ans+=x*m; } else ///ans不是递增时 { ans=(ans+m)%i;///普通求法 i++; } } return (ans+s)%n; } int main() { LL n,m; while(scanf("%lld%lld",&n,&m)!=EOF) { LL ans=solve(n,m,1); printf("%lld\n",ans?ans:n); } return 0; }
时间: 2024-04-26 21:20:16 浏览: 11
这段代码实现了一个求解约瑟夫环问题的函数 `solve`,并在 `main` 函数中多次调用该函数。
具体来说,给定 $n$ 个人和一个数 $m$,这 $n$ 个人围成一圈,从第 $1$ 个人开始报数,报到 $m$ 的人出圈,剩下的人继续从 $1$ 开始报数,直到所有人都出圈。求最后一个出圈的人在初始时的编号。
`solve` 函数中的实现使用了两种方法:
- 当 `ans` 递增时,通过计算每次增加的次数,直接跳过一些人,减少不必要的求解。
- 当 `ans` 不递增时,使用普通的求解方法,即 `(ans + m) % i`。
最后,将最后一个出圈的人的编号 `ans` 与给定的起始编号 `s` 相加,再对 `n` 取模,即为最终答案。
相关问题
#include<iostream> #include<cstdio> using namespace std;是什么意思
#include<iostream> #include<cstdio> using namespace std; 是C++中的预处理指令,用于引入头文件和命名空间。
1. #include<iostream> 是引入iostream头文件,其中包含了输入输出流的定义,例如cout和cin等。
2. #include<cstdio> 是引入cstdio头文件,其中包含了C语言标准输入输出函数的定义,例如printf和scanf等。
3. using namespace std; 是使用std命名空间,std是C++标准库的命名空间,其中包含了很多常用的函数和类。
这些预处理指令的作用是为了在程序中能够使用输入输出流和标准库函数,使得程序更加方便和简洁。
#include<cstdio> #include<cstring> #include<algorithm> #include<stack>
`#include<cstdio>`、`#include<cstring>`、`#include<algorithm>`和`#include<stack>`是C++编程语言中的预处理指令,用于包含相应的头文件。这些头文件提供了一些常用的函数和类,以便在程序中使用。
1. `#include<cstdio>`:这个头文件包含了C标准输入输出库(C Standard Input/Output Library),提供了对文件和流进行操作的函数,如`printf()`、`scanf()`等。
2. `#include<cstring>`:这个头文件包含了C字符串处理库(C String Library),提供了对字符串进行操作的函数,如`strcpy()`、`strlen()`等。
3. `#include<algorithm>`:这个头文件包含了C++标准算法库(C++ Standard Algorithm Library),提供了一些常用的算法,如排序、查找等。
4. `#include<stack>`:这个头文件包含了C++标准栈库(C++ Standard Stack Library),提供了栈数据结构及其相关操作,如入栈、出栈等。