[CSP-S模拟测试]:嘟嘟噜（约瑟夫问题）

题目描述

由于众所周知的原因，冈部一直欠真由理一串香蕉。
为了封上真由理的嘴，冈部承诺只要真由理回答出这个问题，就给她买一车的香蕉：
一开始有$n$个人围成一个圈，从$1$开始顺时针报数，报出$m$的人被机关处决。然后下一个人再从$1$开始报数，直到只剩下一个人。
红莉栖：“这不就是约瑟夫问题吗...”
伦太郎：“助手你给我闭嘴！”
真由理虽然已经晕头转向了，但听到有一车的香蕉，两眼便放出了光芒。
“那个呢，真由氏很想要一车子的香蕉呢。如果可以帮帮我的话，我可以把一些香蕉分给你哟，诶嘿嘿。拜托你啦。”

输入格式

第一行一个整数$T$，表示数据组数。
接下来$T$行，每行两个整数$n,m$。

输出格式

对于每组数据，输出一行一个整数，表示幸存者的编号。

样例

样例输入：

5
4 6
2 8
2 9
8 8
7 9

样例输出：

3
1
2
4
7

数据范围与提示

对于$100\%$的数据，$1\leqslant T\leqslant 20,1\leqslant n\leqslant 10^9,1\leqslant m\leqslant 10^5$。

题解

经典的约瑟夫问题，其式子就是$f_i=(f_{i-1}+m)\mod i$，但是只有$20$分很恐怖，于是我们考虑优化。

发现虽然每一步都在加$m$但是$mod$的次数还是很少的，实际上只有$\log$次，那么我们可以直接计算得到下一次$mod$的位置，然后直接跳过去。

时间复杂度：$\Theta(T\times m\log n)$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

long long n,m;

long long ans;

int main()

{

	int T;scanf("%d",&T);

	while(T--)

	{

		ans=0;

		scanf("%lld%lld",&n,&m);

		for(long long i=1;i<=n;i++)

		{

			long long k=min((i-ans)/m-1,n-i-1);

			if(k>0&&k<n){ans+=k*m;i+=k;}

			ans=(ans+m)%i;

		}

		printf("%lld\n",ans+1);

	}

	return 0;

}

rp++

巴特西