会员或题库专享

购买美团机考编程题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（美团机考编程题库），可解锁完整内容。

购买题库开通会员

关键结论：将角度分数 $\frac{N}{D}$ 约分为 $\frac{N'}{D'}$ ，其中 $D' = D / \gcd(N,D)$ 。该角度在 $B$ -细分体系下能用有限层细分精确表示，当且仅当 $D'$ 的所有质因子都来自 $B$ 。等价地，存在某个正整数 $t$ 使

D' \mid B^t

等价算法：反复用 $\gcd(D', B)$ 去除 $D'$ 中与 $B$ 的公共质因子，直到 $\gcd(D', B) = 1$ 。若最终得到 $D' = 1$ ，则能用有限层细分精确表示，否则不能。

题目内容

小蓝拥有一座古老的星盘，上面均匀地划分着 $B$ 个主刻度，每个主刻度之间又可以继续细分为 $B$ 个更小的刻度，依此类推，可以无限细分。

现在她手上有许多待观测的角度，每个角度用分数 $\frac{N}{D}$ 周（一个周角记作 $1$ ）表示。她想知道，某个给定的角度在这个星盘的 $B$ -细分体系中，是否只需要有限层细分就能被精确表示（即细分到某一层后，角度恰好落在刻度线上，无需继续细分）。

#P3514. 第2题-有限刻度的星盘