Project Euler 195

题目

Inscribed circles of triangles with one angle of $60$ degrees

Let’s call an integer sided triangle with exactly one angle of $60$ degrees a 60-degree triangle.

Let $r$ be the radius of the inscribed circle of such a $60$-degree triangle.

There are $1234$ $60$-degree triangles for which $r\le 100$.

Let $T(n)$ be the number of $60$-degree triangles for which $r\le n$, so $T(100)=1234,T(1000)=22767$ and $T(10000)=359912$.

Find $T(1053779)$.

解决方案

令 $N=1053379$。根据余弦定理，假设三角形两边为长度 $a,b$，第三条边的长度 $c$，其对角为 $60°$，那么 $a,b,c$ 满足：

$$a^2+b^2-ab=c^2$$

这篇文章提到了一种构造出一组本原三元组 $(a,b,c)$（即 $gcd(a,b,c)=1$）满足 $a^2+b^2-ab=c^2$ 的方法：如果 $m>n,gcd(n,m)=1,3\nmid (m-n)$, 那么有：

$$a=2mn+n^2,b=2mn+m^2,c=m^2+n^2+mn(1)$$

或者是

$$a=m^2-n^2,b=2mn+m^2,c=m^2+n^2+mn(2)$$

根据等积法，不难发现内切圆的半径 $r$ 满足 ${\displaystyle \frac{a+b+c}{2}}\cdot r={\displaystyle \frac{1}{2}}ab\sin 60°$。

分别代入式 $(1),(2)$，分别得到

$$r={\displaystyle \frac{\sqrt{3}mn}{2}}(3)$$

$$r={\displaystyle \frac{(m-n)(2n+m)}{2\sqrt{3}}}(4)$$

因此，根据 $(3)(4)$ 式枚举出所有 $r\le N$ 的本原三元组后，计算对应非本原三元组的数量即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1053779;
double eps=1e-8;
double sq3=sqrt(3);
int main() {
    int ans = 0;
    for (int m = 1; 0.5 * sq3 * m <= N; m++) {
        double r;
        for (int n = 1; n < m && (r = 0.5 * sq3 * m * n - eps) <= N; n++) {
            if ((m - n) % 3 && __gcd(m, n) == 1) {
                ans += int(1.0 * N / r + eps);
            }
        }
    }
    double c = 0.5 / sq3;
    for (int n = 1; c * (2 * n + 1) <= N; n++) {
        double r;
        for (int m = n + 1; (r = c * (m - n) * (2 * n + m)  - eps) <= N; m++) {
            if ((m - n) % 3 && __gcd(m, n) == 1) {
                ans += int(1.0 * N / r + eps);
            }
        }
    }
    printf("%d\n", ans);
}