Strange Reflex Game 官方题解
钩七
·
·
题解
设光线第 i 次反射的反射点为 p_i，p_0=A，圆心为 O。
相邻两个反射点与 $O$ 连线的圆心角 $\angle{p_{i-1}Op_i}=180-2\alpha = 2x$，可知所有符合上述定义的圆心角均相等，设为 $\beta$。
问题转化为一个点初始位于 $A$，每次旋转圆心角大小为 $\beta = 2x$，旋转 $n$ 次之后第一次回到 $A$，求 $n-1$ 的数值。
由上述描述有，求最小的 $n$ 满足 $\exists k \in \mathbb{Z} ,2n x=360k$。
### Subtask 1-3
手动模拟一下即可。
- $n=2,k=1,180n=360k$。
- $n=4,k=1,90n=360k$。
- $n=20,k=7,126n=360k$。
### Subtask 4
因为分母是 $1$，则 $n \le 360$，直接枚举检查是否是 $360$ 的倍数即可，复杂度 $O(360T)$。
### Subtask 5
我们发现 $n$ 是 $2x$ 和 $360$ 的最小公倍数除以 $2x$，即
$$
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(T \log V)$。
### 代码
```
#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;
}
```