#P07752. 夏令营旗手

Description

2022年湖南省《信息与未来》小学夏令营将在衡阳市八中进行，组委会决定在衡阳市八中的学生中推选一名旗手，推选方法如下：

衡阳市八中有n名学生（1<=n<=1000）。每名学生有一个学号，学号为(1,2,3,4......n)。同时，每名同学有一张选票，可以推选一名同学为旗手。最后，得票最多者当选，若得票最多者相同票数，则学号小者当选。

例如n=8，选票为2 3 4 4 3 4 1 6，4号学生得票最多（3票）当选小旗手。

Input

n和x1两个整数，n为学生数，x1为第一个选票上的学号，之后的选票Xi(i>=2)由下面的递推关系给出：

Xi=((X(i-1)*37+33031)% n)+1

根据这个公式，就能从X1推导出X2,X3,X4.......Xn.

Output

一个整数，即选出的旗手的学号。

Samples

输入数据 1

5  2

Copy

输出数据 1

2

Copy

Limitation

1s, 1024KiB for each test case.

思路：

根据递推式Xi=((X(i-1)*37+33031)% n)+1，直接带入求值。

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,x1,x[1001],f[1001];
	memset(x,0,sizeof(x));
	memset(f,0,sizeof(f));
	cin>>n>>x1;
	x[1]=x1;
	for(int i=2;i<=n;i++)
	{
		x[i]=((x[i-1]*37+33031)%n)+1;
	}
	for(int i=1;i<=n;i++)
	{
		f[x[i]]++;
	}
	int max=-1,ans;
	for(int i=1;i<=n;i++)
	{
		if(f[i]>max)
		{
			max=f[i];
			ans=i;
		} 
	}
	cout<<ans;
	return 0;
}
//Xi=((X(i-1)*37+33031)% n)+1