题面描述
小明报名参加了趣味运动会，运动会游戏规则如下：在一个环形跑道上，等距离放置着 N 个小球，小球按照顺时针方向从起点开始依次编号为 1 到 N ，在最短时间内取走放在跑道上尽可能多小球的选手获胜。举办方要求每个选手只能按照顺时针方向，跳过 M-1 个号码取后走下一个小球。如当 N=5 、 M=3 时，小明能够取走所有的小球，取走的顺序依次为 1->4->2->5->3 。当 N=6 、 M=2 时，小明只能取走 3 个小球 1->3->5 。小明想知道在一场比赛中他最多能取走多少小球，当然，小明是知道怎么做的，但是他忙着补作业，所以这个简单的问题就交 (shuai guo) 给你了。
输入数据
输入数据的第一行为一个整数 T ，表示有 T 组测试样例。每组样例为单独的一行，包括两个整数 N 和 M 。
输出数据
对每一组输入数据，输出一行结果 ”Case #id: M” ，表示第 id 组数据的结果是 M ， id 从 1 开始。
样例输入
3
5 3
6 2
10 6
样例输出
Case #1: 5
Case #2: 3
Case #3: 5
我的解法（可以实现，但是效率低）
T = int(input())for M in range(T) :dArray = []inputStr = input() if inputStr != "":ns = inputStr.split() N = int(ns[0]) step = int(ns[1]) p = 1 for n in range(N-len(dArray)): if p > N:p = p - N if p in dArray:break else:dArray.append(p)p = p + step M = M + 1 print("Case #%d: %d" % (M,len(dArray)))else: break
推荐解法（辗转相除法求最大公约数）
心得：复杂度问题，通过最大公约数加速遍历
def gcd(a, b): #辗转相除法求最大公约数if b == 0: return a else: return gcd(b, a%b)T = int(input())for n in range(T) :dArray = [] inputStr = input() if inputStr != "": ns = inputStr.split() N = int(ns[0]) M = int(ns[1]) result = gcd(N, M) print("Case #%d: %d" % (n + 1 , N / result)) else: break
绕圆圈：小明报名参加了趣味运动会 运动会游戏规则如下：在一个环形跑道上 等距离放置着 N 个小球 小球按照顺时针方向从起点开始依次编号为 1 到 N 在最短时间内取走放在跑道上尽可能多小球的选手获胜
如果觉得《绕圆圈：小明报名参加了趣味运动会 运动会游戏规则如下：在一个环形跑道上 等距离放》对你有帮助，请点赞、收藏，并留下你的观点哦！
