P14138 Strange Reflex Game 题解

· · 题解

题意简介

原题很简洁了，所以不简介了

link

思路及做法

我们由题意以及弦切角定理可知，若正整数 n \ge 2 使得 2nx^\circ = 360k^\circ ，则光线经过 (n-1) 次反射后回到起始点，其中 k 是正整数。

这里的系数 2 是圆周角转化至圆心角带来的，可以对 x 乘以 2，即对 p 乘以 2。

接下来我们就要考虑怎样的 n 会让上式最小。而 x,360 都是常数，所以 nxq = np = 360kq 要取最小值即 p,360q 的最小公倍数。注意这里两边同乘了给定常数 q 化成整数。

而p,360q 的最小公倍数可直接用STL函数表示为 \frac{360pq}{\_\_gcd(p,360q)} 。

代入原式，最小的 n = \frac{360pq}{\_\_gcd(p,360q) \cdot p} = \frac{360q}{\_\_gcd(p,360q)}。

直接计算即可，记得开long long并且输出减 1 就可以了。

赛时AC代码


#include<bits/stdc++.h>
using namespace std;
#define ll long long
int t;
int main()
{
    cin>>t;
    while(t--)
    {
        ll p,q;
        cin>>p>>q;
        p*=2;
        ll k=__gcd(p,q);
        p/=k,q/=k;
        ll ans=(360*q/__gcd(p,360*q));
        cout<<ans-1<<endl;
    }
    return 0;
}

Last Update： 2025/10/03 20:47