Project Euler 279

题目

Triangles with integral sides and an integral angle

How many triangles are there with integral sides, at least one integral angle (measured in degrees), and a perimeter that does not exceed \(10^8\)?

解决方案

可以知道，一个角为整数的情况下，仅有\(60°,90°,120°\)才满足题意。因此，本题综合了第75, 143, 195题的所有成果。直接使用它们的方法计算各自的三角形个数即可。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100000000;
int f1(int m,int n){return 5*m*n+2*m*m+2*n*n;}
int f2(int m,int n){return 3*m*n+3*m*m;}
int f3(int m,int n){return 3*m*n+2*m*m+n*n;}
int f4(int m,int n){return m*m+m*n;}
int main(){
    // 等腰三角形的情况
    ll ans=N/3;
    // 60
    for(int m=2;f1(m,1)<=N;m++){
        for(int n=1,r;n<m&&(r=f1(m,n))<=N;n++){
            if((m-n)%3&&__gcd(n,m)==1) ans+=N/r;
        }
    }
    for(int m=2;f2(m,1)<=N;m++){
        for(int n=1,r;n<m&&(r=f2(m,n))<=N;n++){
            if((m-n)%3&&__gcd(n,m)==1) ans+=N/r;
        }
    }
    // 120
    for(int m=2;f3(m,1)<=N;m++){
        for(int n=1,r;n<m&&(r=f3(m,n))<=N;n++){
            if((m-n)%3&&__gcd(n,m)==1) ans+=N/r;
        }
    }
    // 90
    for(int m=3; f4(m,1)<=N;m+=2)
        for(int n=1,r;n<m&&(r=f4(m,n))<=N;n+=2){
            if(__gcd(n,m)==1) ans+=N/r;
        }
    printf("%lld\n",ans);
}

使用Stern-Brocot Tree可以优化多次计算最大公因数的过程：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100000000;
ll ans=N/3;
void dfs(int lu,int ld,int ru,int rd){
    int n=lu+ru,m=ld+rd;
    ll f1=5ll*m*n+2*m*m+2*n*n;
    ll f2=3ll*m*n+3*m*m;
    ll f3=3ll*m*n+2*m*m+n*n;
    ll f4=1ll*m*m+m*n;
    if(f1>N&&f2>N&&f3>N&&f4>N) return;
    if((n-m)%3) ans+=1ll*N/f1+N/f2+N/f3;
    if(n&m&1) ans+=N/f4;
    dfs(lu,ld,n,m);
    dfs(n,m,ru,rd);
}
int main(){
    dfs(0,1,1,1);
    printf("%d\n",ans);
}