题目描述
由于众所周知的原因，冈部一直欠真由理一串香蕉。
为了封上真由理的嘴，冈部承诺只要真由理回答出这个问题，就给她买一车的香蕉：
一开始有$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\%$的数据，$1leqslant Tleqslant 20,1leqslant nleqslant 10^9,1leqslant mleqslant 10^5$。
题解
经典的约瑟夫问题，其式子就是$f_i=(f_{i-1}+m)mod i$，但是只有$20$分很恐怖，于是我们考虑优化。
发现虽然每一步都在加$m$但是$mod$的次数还是很少的，实际上只有$log$次，那么我们可以直接计算得到下一次$mod$的位置，然后直接跳过去。
时间复杂度：$Theta(T imes mlog 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
",ans+1);
}
return 0;
}
rp++