
有一份题解提出了为什么用
2π−最初选的两个角
- 原理应该是,取的三个角必须覆盖整个圆,
按照正确的思路,应该是(下边加了*的角代表取了>180度的那个角):gcd(∠AOC,∠BOC,∠AOB∗)
下面证明一个东西:先取
∠AOB,∠AOC做
gcd和先取
∠COB,∠AOC做
gcd是一样的:
gcd(∠AOB,∠AOC)=gcd(∠AOC+COB,∠AOC)=gcd(∠COB,∠AOC)
如果一开始取的两个角不重叠,肯定能得到正确的答案。如果重叠呢?
我们只需要证明,一开始取的两个角是重叠的时候,第一次的
gcd得到的结果和 (
2π - 第一次取的两个角)做
gcd 和
∠AOB∗做
gcd是一样的就可以证明是正确答案了。
证明:
然后如果一开始取的角是两个重叠的,
比如角
∠AOB和
∠AOC,那么你得到的第一次
gcd肯定是
∠AOC,
这时候再和
∠BOC′(2
π - 第一次取的两个角)做
gcd的式子就是:
gcd(∠AOC,∠BOC′)=gcd(∠AOC,∠BOA∗−∠AOC′)=gcd(∠AOC,∠BOA∗−∠AOC)=gcd(∠AOC,∠BOA∗)
C′为
C关于
AB对称的点