本文共 1521 字，大约阅读时间需要 5 分钟。
题目大意：
n个人，从第m个人开始报数，报到k的人出局，问最后剩余的人是第几号
题解：
本题和经典的约瑟夫环问题相比，就是从第m个人开始报数了，经典的是从第1个开始
那我们可以看作，把约瑟夫环左移m次，把第m个人移成第1个人.还要注意这个题是，第m个人首先出局，而不是报k个再出局，所以我们可以看作是从第m-k个人开始报数的
也就是说，在最后的f[n]+1 变成f[n]+1+m-k
f[n]+1+m-k万一k很大就会是负的，所以要给它+n变成正的再取模
我做的时候担心k可能很大，一次+n有可能不够，所以就一直+n到结果为正数为止
其实是不用的，这里顺便学习了一下负数取模
a%b
只要a是负的，结果就是负的；‘’只要a是正的，结果就是正的。而不用管b的正负
并且结果的绝对值一定是[0,b-1]
所以即使f[n]+1+m-k是个很大值的负数，对n取模之后也是出去[0,n-1]，再+n绝对为正
我自己还WA了一发，wa在最后结果ans=0的情况上，因为编号是1-n的，所以ans=0的话其实应该ans=n
写法1
#include#include #include #define ll long long#define INF 1000000007#define eps 1e-6#define mod 1000000007#define double long doubleusing namespace std;ll f[100010];int main(){ //freopen("input.txt","r",stdin); int n,k,m; ll ans; while(cin>>n>>k>>m) { if(n==0 && k==0 && m==0)return 0; f[1]=0; for(int i=2;i<=n;++i) { f[i]=(f[i-1]+k)%i; } ans=f[n]+1+m-k; while(ans<0)ans+=n; ans%=n; if(ans==0)ans=n; cout< <
写法2
#include#include #include #define ll long long#define INF 1000000007#define eps 1e-6#define mod 1000000007#define double long doubleusing namespace std;ll f[100010];int main(){ //freopen("input.txt","r",stdin); int n,k,m; ll ans; while(cin>>n>>k>>m) { if(n==0 && k==0 && m==0)return 0; f[1]=0; for(int i=2;i<=n;++i) { f[i]=(f[i-1]+k)%i; } ans=f[n]+1+m-k; ans%=n; if(ans<=0)ans+=n; cout< <
转载地址：http://syfgf.baihongyu.com/