{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv\u003e \n \u003cstyle type\u003d\"text/css\"\u003e\n #problem-ul-reset{\n list-style-position: inside;\n list-style-type: decimal;\n margin: 15px;\n }\n #problem-ul-reset li { margin:5px 0; }\n #prog-content img { width: 35%; }\n\u003c/style\u003e \n \u003cdiv id\u003d\"prog-content\"\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e描述\u003c/h4\u003e \n \u003cp\u003e小Hi和小Ho的班级正在进行班长的选举,他们决定通过一种特殊的方式来选择班长。\u003c/p\u003e \n \u003cp\u003e首先N个候选人围成一个圈,依次编号为0..N-1。然后随机抽选一个数K,并0号候选人开始按从1到K的顺序依次报数,N-1号候选人报数之后,又再次从0开始。当有人报到K时,这个人被淘汰,从圈里出去。下一个人从1开始重新报数。\u003c/p\u003e \n \u003cp\u003e也就是说每报K个数字,都会淘汰一人。这样经过N-1轮报数之后,圈内就只剩下1个人了,这个人就作为新的班长。\u003c/p\u003e \n \u003cp\u003e举个例子,假如有5个候选人,K\u003d3:\u003c/p\u003e \n \u003cpre\u003e初始\n0: 0 1 2 3 4\n从0号开始报数,第1次是2号报到3\n1: 0 1 - 3 4 \t// 0 1 2, 2号候选人淘汰\n从3号开始报数,第2次是0号报到3\n2: - 1 3 4\t\t// 3 4 0, 0号候选人淘汰\n从1号开始报数,第3次是4号报到3\n3: 1 3 -\t\t// 1 3 4, 4号候选人淘汰\n从1号开始报数,第4次是1号报到3\n4: - 3\t\t\t// 1 3 1, 1号候选人淘汰\n \u003c/pre\u003e \n \u003cp\u003e对于N\u003d5,K\u003d3的情况,最后当选班长的人是编号为3的候选人。\u003c/p\u003e \n \u003cp\u003e小Ho:小Hi,我觉得当人数和K都确定的时候已经可以确定结果了。\u003c/p\u003e \n \u003cp\u003e小Hi:嗯,没错。\u003c/p\u003e \n \u003cp\u003e小Ho:我也想当班长,小Hi你能提前告诉我应该站在哪个位置么?\u003c/p\u003e \n \u003cp\u003e小Hi:我可以告诉你怎么去求最后一个被淘汰的位置,不过具体的值你得自己去求解。\u003c/p\u003e \n \u003cp\u003e小Ho:嗯,没问题,那么你快告诉我方法吧!\u003c/p\u003e \u003c!-- Button trigger modal --\u003e \n \u003cp\u003e\u003ca href\u003d\"#\" data-toggle\u003d\"modal\" data-target\u003d\"#m2\"\u003e提示:约瑟夫问题\u003c/a\u003e\u003c/p\u003e \u003c!-- Modal --\u003e \n \u003cdiv class\u003d\"modal\" id\u003d\"m2\" tabindex\u003d\"-1\" role\u003d\"dialog\" aria-labelledby\u003d\"myModalLabel\" aria-hidden\u003d\"true\"\u003e \n \u003cdiv class\u003d\"modal-dialog\" style\u003d\"width: 870px;\"\u003e \n \u003cdiv class\u003d\"modal-content\"\u003e \n \u003cdiv class\u003d\"modal-header\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"close\" data-dismiss\u003d\"modal\" aria-label\u003d\"Close\"\u003e\u003cspan aria-hidden\u003d\"true\"\u003e×\u003c/span\u003e\u003c/button\u003e \n \u003ch4 class\u003d\"modal-title\" id\u003d\"myModalLabel\"\u003e提示:约瑟夫问题\u003c/h4\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-body\"\u003e \n \u003cp\u003e小Hi:这个问题其实还蛮有名的,它被称为约瑟夫的问题。\u003c/p\u003e \n \u003cp\u003e最直观的解法是用循环链表模拟报数、淘汰的过程,复杂度是O(NM)。\u003c/p\u003e \n \u003cp\u003e今天我们来学习两种更高效的算法,一种是递推,另一种也是递推。第一种递推的公式为:\u003c/p\u003e \n \u003cpre\u003e令f[n]表示当有n个候选人时,最后当选者的编号。\nf[1] \u003d 0\nf[n] \u003d (f[n - 1] + K) mod n\n\t\t\u003c/pre\u003e \n \u003cp\u003e接下来我们用数学归纳法来证明这个递推公式的正确性:\u003c/p\u003e \n \u003cp\u003e(1) \u003cb\u003ef[1] \u003d 0\u003c/b\u003e\u003c/p\u003e \n \u003cp\u003e显然当只有1个候选人时,该候选人就是当选者,并且他的编号为0。\u003c/p\u003e \n \u003cp\u003e(2) \u003cb\u003ef[n] \u003d (f[n - 1] + K) mod n\u003c/b\u003e\u003c/p\u003e \n \u003cp\u003e假设我们已经求解出了f[n - 1],并且保证f[n - 1]的值是正确的。\u003c/p\u003e \n \u003cp\u003e现在先将n个人按照编号进行排序:\u003c/p\u003e \n \u003cpre\u003e0 1 2 3 ... n-1\n\u003c/pre\u003e \n \u003cp\u003e那么第一次被淘汰的人编号一定是K-1(假设K \u0026lt; n,若K \u0026gt; n则为(K-1) mod n)。将被选中的人标记为\"#\":\u003c/p\u003e \n \u003cpre\u003e0 1 2 3 ... K-2 # K K+1 K+2 ... n-1\n\u003c/pre\u003e \n \u003cp\u003e第二轮报数时,起点为K这个候选人。并且只剩下n-1个选手。假如此时把k+1看作0\u0027,k+2看作1\u0027...\u003c/p\u003e \n \u003cp\u003e则对应有:\u003c/p\u003e \n \u003cpre\u003e 0 1 2 3 ... K-2 # K K+1 K+2 ... n-1\nn-K\u0027 n-2\u0027 0\u0027 1\u0027 2\u0027 ... n-K-1\u0027\n\u003c/pre\u003e \n \u003cp\u003e此时在0\u0027,1\u0027,...,n-2\u0027上再进行一次K报数的选择。而f[n-1]的值已经求得,因此我们可以直接求得当选者的编号s\u0027。\u003c/p\u003e \n \u003cp\u003e但是,该编号s\u0027是在n-1个候选人报数时的编号,并不等于n个人时的编号,所以我们还需要将s\u0027转换为对应的s。\u003c/p\u003e \n \u003cp\u003e通过观察,s和s\u0027编号相对偏移了K,又因为是在环中,因此得到s \u003d (s\u0027+K) mod n。\u003c/p\u003e \n \u003cp\u003e即f[n] \u003d (f[n-1] + k) mod n。\u003c/p\u003e \n \u003cbr\u003e \n \u003cp\u003e至此递推公式的两个式子我们均证明了其正确性,则对于任意给定的n,我们可以使用该递推式求得f[n],写成伪代码为: \u003c/p\u003e \n \u003cpre\u003eJosephus(N, K):\n\tf[1] \u003d 0\n\tFor i \u003d 2 .. N\n\t\tf[i] \u003d (f[i - 1] + K) mod i\n\tEnd For\n\tReturn f[N]\n\u003c/pre\u003e \n \u003cp\u003e同时由于计算f[i]时,只会用到f[i-1],因此我们还可以将f[]的空间节约,改进后的代码为:\u003c/p\u003e \n \u003cpre\u003eJosephus(N, K):\n\tret \u003d 0\n\tFor i \u003d 2 .. N\n\t\tret \u003d (ret + K) mod i\n\tEnd For\n\tReturn ret\n\u003c/pre\u003e \n \u003cp\u003e该算法的时间复杂度为O(N),空间复杂度为O(1)。对于N不是很大的数据来说,可以解决。\u003c/p\u003e \n \u003cp\u003e小Ho:要是N特别大呢?\u003c/p\u003e \n \u003cp\u003e小Hi:那么我们就可以用第二种递推,解决的思路仍然和上面相同,而区别在于我们每次减少的N的规模不再是1。\u003c/p\u003e \n \u003cp\u003e同样用一个例子来说明,初始N\u003d10,K\u003d4:\u003c/p\u003e \n \u003cp\u003e初始序列:\u003c/p\u003e \n \u003cpre\u003e0 1 2 3 4 5 6 7 8 9\n\u003c/pre\u003e \n \u003cp\u003e当7号进行过报数之后:\u003c/p\u003e \n \u003cpre\u003e0 1 2 - 4 5 6 - 8 9\u003c/pre\u003e \n \u003cp\u003e在这里一轮报数当中,有两名候选人退出了。而对于任意一个N,K来说,退出的候选人数量为N/K(\"/\"运算表示整除,即带余除法取商)\u003c/p\u003e \n \u003cp\u003e由于此时起点为8,则等价于:\u003c/p\u003e \n \u003cpre\u003e2 3 4 - 5 6 7 - 0 1\u003c/pre\u003e \n \u003cp\u003e因此我们仍然可以从f[8]的结果来推导出f[10]的结果。\u003c/p\u003e \n \u003cp\u003e但需要注意的是,此时f[10]的结果并不一定直接等于(f[8] + 8) mod 10。\u003c/p\u003e \n \u003cp\u003e若f[8]\u003d2,对于原来的序列来说对应了0,(2+8) mod 10 \u003d 0,是对应的;若f[8]\u003d6,则有(6+8) mod 10 \u003d 4,然而实际上应该对应的编号为5。\u003c/p\u003e \n \u003cp\u003e这是因为在序列(2 3 4 - 5 6 7 - 0 1)中,数字并不是连续的。\u003c/p\u003e \n \u003cp\u003e \u003c/p\u003e \n \u003cp\u003e因此我们需要根据f[8]的值进行分类讨论。假设f[8]\u003ds,则根据s和N mod K的大小关系有两种情况:\u003c/p\u003e \n \u003cp\u003e \u003c/p\u003e \n \u003cpre\u003e1) s \u0026lt; N mod K : s\u0027 \u003d s - N mod K + N\n2) s ≥ N mod K : s\u0027 \u003d s - N mod K + (s - N mod K) / (K - 1)\n\u003c/pre\u003e \n \u003cp\u003e此外还有一个问题,由于我们不断的在减小N的规模,最后一定会将N减少到小于K,此时N/K\u003d0。\u003c/p\u003e \n \u003cp\u003e因此当N小于K时,就只能采用第一种递推的算法来计算了。\u003c/p\u003e \n \u003cp\u003e最后优化方法的伪代码为:\u003c/p\u003e \n \u003cpre\u003eJosephus(N, K):\n\tIf (N \u003d\u003d 1) Then\n\t\tReturn 0\n\tEnd If\n\tIf (N \u0026lt; K) Then\n\t\tret \u003d 0\n\t\tFor i \u003d 2 .. N\n\t\t\tret \u003d (ret + K) mod i\n\t\tEnd For\n\t\tReturn ret\n\tEnd If \n\tret \u003d Josephus(N - N / K, K);\n\tIf (ret \u0026lt; N mod K) Then \n\t\tret \u003d ret - N mod K + N\n\tElse\n\t\tret \u003d ret - N mod K + (ret - N mod K) / (K - 1)\n\tEnd If\n\tReturn ret\n\u003c/pre\u003e \n \u003cp\u003e改进后的算法可以很快将N的规模减小到K,对于K不是很大的问题能够快速求解。\u003c/p\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-footer\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"btn btn-default\" data-dismiss\u003d\"modal\"\u003eClose\u003c/button\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e输入\u003c/h4\u003e \n \u003cp\u003e第1行:1个正整数t,表示多组输入数据,1≤t≤100\u003c/p\u003e \n \u003cp\u003e第2..t+1行:每行2个正整数n,k,第i+1行表示第i组测试数据,2≤n≤1,000,000,000。2≤k≤1,000\u003c/p\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e输出\u003c/h4\u003e \n \u003cp\u003e第1..t行:每行1个整数,第i行表示第i组数据的解\u003c/p\u003e \n \u003c/div\u003e \n\u003c/div\u003e \n\u003cdt\u003e\n Sample Input \n\u003c/dt\u003e \n\u003cdd\u003e \n \u003cpre\u003e2\r\n5 3\r\n8 3\u003c/pre\u003e \n\u003c/dd\u003e \n\u003cdt\u003e\n Sample Output \n\u003c/dt\u003e \n\u003cdd\u003e \n \u003cpre\u003e3\r\n6\u003c/pre\u003e \n\u003c/dd\u003e\n\u003cdiv\u003e \n \u003cstyle type\u003d\"text/css\"\u003e\n #problem-ul-reset{\n list-style-position: inside;\n list-style-type: decimal;\n margin: 15px;\n }\n #problem-ul-reset li { margin:5px 0; }\n #prog-content img { width: 35%; }\n\u003c/style\u003e \n \u003cdiv id\u003d\"prog-content\"\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e描述\u003c/h4\u003e \n \u003cp\u003e小Hi和小Ho的班级正在进行班长的选举,他们决定通过一种特殊的方式来选择班长。\u003c/p\u003e \n \u003cp\u003e首先N个候选人围成一个圈,依次编号为0..N-1。然后随机抽选一个数K,并0号候选人开始按从1到K的顺序依次报数,N-1号候选人报数之后,又再次从0开始。当有人报到K时,这个人被淘汰,从圈里出去。下一个人从1开始重新报数。\u003c/p\u003e \n \u003cp\u003e也就是说每报K个数字,都会淘汰一人。这样经过N-1轮报数之后,圈内就只剩下1个人了,这个人就作为新的班长。\u003c/p\u003e \n \u003cp\u003e举个例子,假如有5个候选人,K\u003d3:\u003c/p\u003e \n \u003cpre\u003e初始\n0: 0 1 2 3 4\n从0号开始报数,第1次是2号报到3\n1: 0 1 - 3 4 \t// 0 1 2, 2号候选人淘汰\n从3号开始报数,第2次是0号报到3\n2: - 1 3 4\t\t// 3 4 0, 0号候选人淘汰\n从1号开始报数,第3次是4号报到3\n3: 1 3 -\t\t// 1 3 4, 4号候选人淘汰\n从1号开始报数,第4次是1号报到3\n4: - 3\t\t\t// 1 3 1, 1号候选人淘汰\n \u003c/pre\u003e \n \u003cp\u003e对于N\u003d5,K\u003d3的情况,最后当选班长的人是编号为3的候选人。\u003c/p\u003e \n \u003cp\u003e小Ho:小Hi,我觉得当人数和K都确定的时候已经可以确定结果了。\u003c/p\u003e \n \u003cp\u003e小Hi:嗯,没错。\u003c/p\u003e \n \u003cp\u003e小Ho:我也想当班长,小Hi你能提前告诉我应该站在哪个位置么?\u003c/p\u003e \n \u003cp\u003e小Hi:我可以告诉你怎么去求最后一个被淘汰的位置,不过具体的值你得自己去求解。\u003c/p\u003e \n \u003cp\u003e小Ho:嗯,没问题,那么你快告诉我方法吧!\u003c/p\u003e \u003c!-- Button trigger modal --\u003e \n \u003cp\u003e\u003ca href\u003d\"#\" data-toggle\u003d\"modal\" data-target\u003d\"#m2\"\u003e提示:约瑟夫问题\u003c/a\u003e\u003c/p\u003e \u003c!-- Modal --\u003e \n \u003cdiv class\u003d\"modal\" id\u003d\"m2\" tabindex\u003d\"-1\" role\u003d\"dialog\" aria-labelledby\u003d\"myModalLabel\" aria-hidden\u003d\"true\"\u003e \n \u003cdiv class\u003d\"modal-dialog\" style\u003d\"width: 870px;\"\u003e \n \u003cdiv class\u003d\"modal-content\"\u003e \n \u003cdiv class\u003d\"modal-header\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"close\" data-dismiss\u003d\"modal\" aria-label\u003d\"Close\"\u003e\u003cspan aria-hidden\u003d\"true\"\u003e×\u003c/span\u003e\u003c/button\u003e \n \u003ch4 class\u003d\"modal-title\" id\u003d\"myModalLabel\"\u003e提示:约瑟夫问题\u003c/h4\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-body\"\u003e \n \u003cp\u003e小Hi:这个问题其实还蛮有名的,它被称为约瑟夫的问题。\u003c/p\u003e \n \u003cp\u003e最直观的解法是用循环链表模拟报数、淘汰的过程,复杂度是O(NM)。\u003c/p\u003e \n \u003cp\u003e今天我们来学习两种更高效的算法,一种是递推,另一种也是递推。第一种递推的公式为:\u003c/p\u003e \n \u003cpre\u003e令f[n]表示当有n个候选人时,最后当选者的编号。\nf[1] \u003d 0\nf[n] \u003d (f[n - 1] + K) mod n\n\t\t\u003c/pre\u003e \n \u003cp\u003e接下来我们用数学归纳法来证明这个递推公式的正确性:\u003c/p\u003e \n \u003cp\u003e(1) \u003cb\u003ef[1] \u003d 0\u003c/b\u003e\u003c/p\u003e \n \u003cp\u003e显然当只有1个候选人时,该候选人就是当选者,并且他的编号为0。\u003c/p\u003e \n \u003cp\u003e(2) \u003cb\u003ef[n] \u003d (f[n - 1] + K) mod n\u003c/b\u003e\u003c/p\u003e \n \u003cp\u003e假设我们已经求解出了f[n - 1],并且保证f[n - 1]的值是正确的。\u003c/p\u003e \n \u003cp\u003e现在先将n个人按照编号进行排序:\u003c/p\u003e \n \u003cpre\u003e0 1 2 3 ... n-1\n\u003c/pre\u003e \n \u003cp\u003e那么第一次被淘汰的人编号一定是K-1(假设K \u0026lt; n,若K \u0026gt; n则为(K-1) mod n)。将被选中的人标记为\"#\":\u003c/p\u003e \n \u003cpre\u003e0 1 2 3 ... K-2 # K K+1 K+2 ... n-1\n\u003c/pre\u003e \n \u003cp\u003e第二轮报数时,起点为K这个候选人。并且只剩下n-1个选手。假如此时把k+1看作0\u0027,k+2看作1\u0027...\u003c/p\u003e \n \u003cp\u003e则对应有:\u003c/p\u003e \n \u003cpre\u003e 0 1 2 3 ... K-2 # K K+1 K+2 ... n-1\nn-K\u0027 n-2\u0027 0\u0027 1\u0027 2\u0027 ... n-K-1\u0027\n\u003c/pre\u003e \n \u003cp\u003e此时在0\u0027,1\u0027,...,n-2\u0027上再进行一次K报数的选择。而f[n-1]的值已经求得,因此我们可以直接求得当选者的编号s\u0027。\u003c/p\u003e \n \u003cp\u003e但是,该编号s\u0027是在n-1个候选人报数时的编号,并不等于n个人时的编号,所以我们还需要将s\u0027转换为对应的s。\u003c/p\u003e \n \u003cp\u003e通过观察,s和s\u0027编号相对偏移了K,又因为是在环中,因此得到s \u003d (s\u0027+K) mod n。\u003c/p\u003e \n \u003cp\u003e即f[n] \u003d (f[n-1] + k) mod n。\u003c/p\u003e \n \u003cbr\u003e \n \u003cp\u003e至此递推公式的两个式子我们均证明了其正确性,则对于任意给定的n,我们可以使用该递推式求得f[n],写成伪代码为: \u003c/p\u003e \n \u003cpre\u003eJosephus(N, K):\n\tf[1] \u003d 0\n\tFor i \u003d 2 .. N\n\t\tf[i] \u003d (f[i - 1] + K) mod i\n\tEnd For\n\tReturn f[N]\n\u003c/pre\u003e \n \u003cp\u003e同时由于计算f[i]时,只会用到f[i-1],因此我们还可以将f[]的空间节约,改进后的代码为:\u003c/p\u003e \n \u003cpre\u003eJosephus(N, K):\n\tret \u003d 0\n\tFor i \u003d 2 .. N\n\t\tret \u003d (ret + K) mod i\n\tEnd For\n\tReturn ret\n\u003c/pre\u003e \n \u003cp\u003e该算法的时间复杂度为O(N),空间复杂度为O(1)。对于N不是很大的数据来说,可以解决。\u003c/p\u003e \n \u003cp\u003e小Ho:要是N特别大呢?\u003c/p\u003e \n \u003cp\u003e小Hi:那么我们就可以用第二种递推,解决的思路仍然和上面相同,而区别在于我们每次减少的N的规模不再是1。\u003c/p\u003e \n \u003cp\u003e同样用一个例子来说明,初始N\u003d10,K\u003d4:\u003c/p\u003e \n \u003cp\u003e初始序列:\u003c/p\u003e \n \u003cpre\u003e0 1 2 3 4 5 6 7 8 9\n\u003c/pre\u003e \n \u003cp\u003e当7号进行过报数之后:\u003c/p\u003e \n \u003cpre\u003e0 1 2 - 4 5 6 - 8 9\u003c/pre\u003e \n \u003cp\u003e在这里一轮报数当中,有两名候选人退出了。而对于任意一个N,K来说,退出的候选人数量为N/K(\"/\"运算表示整除,即带余除法取商)\u003c/p\u003e \n \u003cp\u003e由于此时起点为8,则等价于:\u003c/p\u003e \n \u003cpre\u003e2 3 4 - 5 6 7 - 0 1\u003c/pre\u003e \n \u003cp\u003e因此我们仍然可以从f[8]的结果来推导出f[10]的结果。\u003c/p\u003e \n \u003cp\u003e但需要注意的是,此时f[10]的结果并不一定直接等于(f[8] + 8) mod 10。\u003c/p\u003e \n \u003cp\u003e若f[8]\u003d2,对于原来的序列来说对应了0,(2+8) mod 10 \u003d 0,是对应的;若f[8]\u003d6,则有(6+8) mod 10 \u003d 4,然而实际上应该对应的编号为5。\u003c/p\u003e \n \u003cp\u003e这是因为在序列(2 3 4 - 5 6 7 - 0 1)中,数字并不是连续的。\u003c/p\u003e \n \u003cp\u003e \u003c/p\u003e \n \u003cp\u003e因此我们需要根据f[8]的值进行分类讨论。假设f[8]\u003ds,则根据s和N mod K的大小关系有两种情况:\u003c/p\u003e \n \u003cp\u003e \u003c/p\u003e \n \u003cpre\u003e1) s \u0026lt; N mod K : s\u0027 \u003d s - N mod K + N\n2) s ≥ N mod K : s\u0027 \u003d s - N mod K + (s - N mod K) / (K - 1)\n\u003c/pre\u003e \n \u003cp\u003e此外还有一个问题,由于我们不断的在减小N的规模,最后一定会将N减少到小于K,此时N/K\u003d0。\u003c/p\u003e \n \u003cp\u003e因此当N小于K时,就只能采用第一种递推的算法来计算了。\u003c/p\u003e \n \u003cp\u003e最后优化方法的伪代码为:\u003c/p\u003e \n \u003cpre\u003eJosephus(N, K):\n\tIf (N \u003d\u003d 1) Then\n\t\tReturn 0\n\tEnd If\n\tIf (N \u0026lt; K) Then\n\t\tret \u003d 0\n\t\tFor i \u003d 2 .. N\n\t\t\tret \u003d (ret + K) mod i\n\t\tEnd For\n\t\tReturn ret\n\tEnd If \n\tret \u003d Josephus(N - N / K, K);\n\tIf (ret \u0026lt; N mod K) Then \n\t\tret \u003d ret - N mod K + N\n\tElse\n\t\tret \u003d ret - N mod K + (ret - N mod K) / (K - 1)\n\tEnd If\n\tReturn ret\n\u003c/pre\u003e \n \u003cp\u003e改进后的算法可以很快将N的规模减小到K,对于K不是很大的问题能够快速求解。\u003c/p\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-footer\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"btn btn-default\" data-dismiss\u003d\"modal\"\u003eClose\u003c/button\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e输入\u003c/h4\u003e \n \u003cp\u003e第1行:1个正整数t,表示多组输入数据,1≤t≤100\u003c/p\u003e \n \u003cp\u003e第2..t+1行:每行2个正整数n,k,第i+1行表示第i组测试数据,2≤n≤1,000,000,000。2≤k≤1,000\u003c/p\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e输出\u003c/h4\u003e \n \u003cp\u003e第1..t行:每行1个整数,第i行表示第i组数据的解\u003c/p\u003e \n \u003c/div\u003e \n\u003c/div\u003e \n\u003cdt\u003e\n Sample Input \n\u003c/dt\u003e \n\u003cdd\u003e \n \u003cpre\u003e2\r\n5 3\r\n8 3\u003c/pre\u003e \n\u003c/dd\u003e \n\u003cdt\u003e\n Sample Output \n\u003c/dt\u003e \n\u003cdd\u003e \n \u003cpre\u003e3\r\n6\u003c/pre\u003e \n\u003c/dd\u003e"}}]}