专栏文章

P14138 Strange Reflex Game 题解

汤汤圆0512
P14138题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minpojg2
此快照首次捕获于
2025/12/02 06:19
3 个月前
此快照最后确认于
2025/12/02 06:19
3 个月前
查看原文

题意简介

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

思路及做法

我们由题意以及弦切角定理可知，若正整数 n≥2n \ge 2 使得 2nx∘=360k∘2nx^\circ = 360k^\circ ，则光线经过 (n−1)(n-1) 次反射后回到起始点，其中 kk 是正整数。
这里的系数 22 是圆周角转化至圆心角带来的，可以对 xx 乘以 22，即对 pp 乘以 22。
接下来我们就要考虑怎样的 nn 会让上式最小。而 x,360x,360 都是常数，所以 nxq=np=360kqnxq = np = 360kq 要取最小值即 p,360qp,360q 的最小公倍数。注意这里两边同乘了给定常数 qq 化成整数。
而p,360qp,360q 的最小公倍数可直接用STL函数表示为 360pq__gcd(p,360q)\frac{360pq}{\_\_gcd(p,360q)}。
代入原式，最小的 n=360pq__gcd(p,360q)⋅p=360q__gcd(p,360q)n = \frac{360pq}{\_\_gcd(p,360q) \cdot p} = \frac{360q}{\_\_gcd(p,360q)}。
直接计算即可，记得开long long并且输出减 11 就可以了。

赛时AC代码

CPP

#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

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...