Description

由于眾所周知的原因, 岡部一直欠真由理一串香蕉.
為了封上真由理的嘴, 岡部承諾只要真由理回答出這個(gè)問題, 就給她買一車的香蕉:
一開始有n 個(gè)人圍成一個(gè)圈, 從1 開始順時(shí)針報(bào)數(shù), 報(bào)出m 的人被機(jī)關(guān)處決. 然后下一個(gè)人再從1 開始報(bào)數(shù), 直到只剩下一個(gè)人.
紅莉棲: “這不就是約瑟夫問題嗎…”
倫太郎: “助手你給我閉嘴!”
真由理雖然已經(jīng)暈頭轉(zhuǎn)向了, 但聽到有一車的香蕉, 兩眼便放出了光芒.
“那個(gè)呢, 真由氏很想要一車子的香蕉呢. 如果可以幫幫我的話, 我可以把一些香蕉分給你喲, 誒嘿嘿. 拜托你啦.”

Input

第一行一個(gè)整數(shù)T, 表示數(shù)據(jù)組數(shù).
接下來T 行, 每行兩個(gè)整數(shù)n;m.

Output

對(duì)于每組數(shù)據(jù), 輸出一行一個(gè)整數(shù), 表示幸存者的編號(hào).

Sample Input

5
4 6
2 8
2 9
8 8
7 9

Sample Output

3
1
2
4
7

Data Constraint

Solution

• 經(jīng)典的 Josephus 問題, 參見 Wikipedia 。網(wǎng)址：Josephus Problem

• 設(shè)函數(shù) f(n,m) 表示 n,m 的答案，那么就有：

• 時(shí)間復(fù)雜度 O(m?log?n) 。

Code

#include<cstdio> using namespace std; inline int read() {int X=0,w=1; char ch=0;while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X*w; } inline int f(int x,int y) {if(x==1) return 0;if(x<y) return (f(x-1,y)+y)%x;int x1=x-x/y;return (long long)(f(x1,y)-x%y+x1)%x1*y/(y-1); } int main() {int T=read();while(T--){int n=read(),m=read();printf("%d\n",f(n,m)+1);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的JZOJ 5421. 【NOIP2017提高A组集训10.25】嘟嘟噜的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。