猴子选大王 题解

(大家都能AC我到底为什么写这个

可以先处理m=1的，显然n就是答案。

n<=1000,m<=1000时，模拟一遍报数过程即可，定义pos表示当前位置，cnt表示当前报到的数，out表示出局的猴数。

n<=10000000,m<=10000000时，写出递推式即可：f(n,m)=(f(n-1,m)+m)%n。注意猴子编号从0开始输出时要+1（看题干描述）。

m=2时，可以打表找找规律，当n为2^x时，ans=1。

1   1 3   1 3 5 7

CODE

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,fl[1007];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	if(m==1){
		cout<<n<<'\n';
		return 0;
	}
	if(n<=1000&&m<=1000){
		int cnt=0,out=0,pos=0;
		while(out!=(n-1)){
			pos++;
			if(pos>n)pos=1;
			if(!fl[pos])cnt++;
			if(cnt==m){
				cnt=0;
				fl[pos]=1;
				out++;
			}
		};
		for(int i = 1;i<=n;i++)if(!fl[i])cout<<i<<'\n';
		return 0;
	}
	if(n<=10000000&&m<=10000000){
		int ans=0;
  		for(int i = 1;i<=n;i++)ans=(ans+m)%i;
  		cout<<ans+1<<'\n';
  		return 0;
	}
	if(m==2){
		for(int i = 31;i>=0;i--) {
			if((1ll<<i)<=n){
				int b=(1ll<<i);
				cout<<(n-b)*2+1<<'\n';
				return 0;
			}
		}
	}
	return 0;
}

（写个题解警示m=2没想出来的自己