专栏文章

Strange Reflex Game 官方题解

wwaauto
P14138题解参与者 8已保存评论 9

文章操作

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

当前评论
9 条
当前快照
1 份
快照标识符
@minplunt
此快照首次捕获于
2025/12/02 06:17
3 个月前
此快照最后确认于
2025/12/02 06:17
3 个月前
查看原文
设光线第 ii 次反射的反射点为 pip_i，p0=Ap_0=A，圆心为 OO。
∀1≤i\forall 1 \le i，∠Opi−1pi=∠Opipi−1=∠Opipi+1\angle{Op_{i-1}p_i} = \angle{Op_ip_{i-1}} = \angle{Op_ip_{i+1}}，可知所有入射角与所有反射角均相等，且等于 90−x90-x，设为 α\alpha。
相邻两个反射点与 OO 连线的圆心角 ∠pi−1Opi=180−2α=2x\angle{p_{i-1}Op_i}=180-2\alpha = 2x，可知所有符合上述定义的圆心角均相等，设为 β\beta。
问题转化为一个点初始位于 AA，每次旋转圆心角大小为 β=2x\beta = 2x，旋转 nn 次之后第一次回到 AA，求 n−1n-1 的数值。
由上述描述有，求最小的 nn 满足 ∃k∈Z,2nx=360k\exists k \in \mathbb{Z} ,2n x=360k。

Subtask 1-3

手动模拟一下即可。
  • n=2,k=1,180n=360kn=2,k=1,180n=360k。
  • n=4,k=1,90n=360kn=4,k=1,90n=360k。
  • n=20,k=7,126n=360kn=20,k=7,126n=360k。

Subtask 4

因为分母是 11，则 n≤360n \le 360，直接枚举检查是否是 360360 的倍数即可，复杂度 O(360T)O(360T)。

Subtask 5

我们发现 nn 是 2x2x 和 360360 的最小公倍数除以 2x2x，即
n=lcm⁡(2pq,360)2pq=lcm⁡(2p,360q)2p=2p⋅360qgcd⁡(2p,360q)⋅2p=360qgcd⁡(2p,360q)n = \frac{\operatorname{lcm}(\frac{2p}{q},360)}{\frac{2p}{q}}=\frac{\operatorname{lcm}(2p,360q)}{2p}=\frac{2p \cdot 360q}{\operatorname{gcd}(2p,360q) \cdot 2p}=\frac{360q}{\operatorname{gcd}(2p,360q)}
辗转相除法计算即可，复杂度 O(Tlog⁡V)O(T \log V)。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
long long tt,p,q,x,y;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>tt;
    for(int o=1;o<=tt;o++){
        cin>>p>>q; x=2*p,y=360*q;
        cout<<y/__gcd(x,y)-1<<"\n";
    }
    return 0;
}

评论

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

正在加载评论...