Project Euler 309

题目

Integer Ladders

In the classic “Crossing Ladders” problem, we are given the lengths \(x\) and \(y\) of two ladders resting on the opposite walls of a narrow, level street. We are also given the height \(h\) above the street where the two ladders cross and we are asked to find the width of the street \((w)\).

Here, we are only concerned with instances where all four variables are positive integers.

For example, if \(x = 70, y = 119\) and \(h = 30\), we can calculate that \(w = 56\). In fact, for integer values \(x, y, h\) and \(0 < x < y < 200\), there are only five triplets \((x,y,h)\) producing integer solutions for \(w\):

\((70, 119, 30), (74, 182, 21), (87, 105, 35), (100, 116, 35)\) and \((119, 175, 40)\).

For integer values \(x, y, h\) and \(0 < x < y < 1 000 000\), how many triplets \((x,y,h)\) produce integer solutions for \(w\)?

解决方案

令\(N=10^6\)。

给上图添加一些变量，如下图所示

根据两对直角三角形的相似性，得到

\[\dfrac{h}{w_1}=\dfrac{b}{w},\dfrac{h}{w_2}=\dfrac{a}{w}\]

通过\(w_1+w_2=w\)消去\(w_1,w_2\)，得到

\[\dfrac{1}{a}+\dfrac{1}{b}=\dfrac{1}{h}\]

由上面的式子可以得到\(h=\dfrac{ab}{a+b}.\)

结合勾股定理\(x^2=b^2+w^2,y^2=a^2+w^2\)，有\(b=\sqrt{x^2-w^2},a=\sqrt{y^2-w^2}\)。

那么，我们可以按照如下算法来寻找这些解：枚举所有勾股三元组\(t,u,v\)满足\(v<10^6\)，并且数组\(g[s]\)存储这些满足\(t=s\lor u=s\)的另一条直角边。然后枚举数组\(g[w]\)中的任意两条不同直角边\((a,b)\)，判断\(a+b\)是否整除\(ab\)即可。

由于直角三角形非常分散，因此\(g[w]\)数组的长度非常短。由此暴力枚举，得出结果的时间非常快。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000000;
vector<int>g[N+4];
int main(){
    for(int s=3;s*s/2<=N;s+=2){
        for(int t=1;t<s&&(s*s+t*t)/2<=N;t+=2){
            if(__gcd(s,t)==1){
                int x=s*t,y=(s*s-t*t)>>1,z=(s*s+t*t)>>1;
                for(int k=1;k*z<N;k++){
                    g[k*x].push_back(k*y);
                    g[k*y].push_back(k*x);
                }

            }
        }
    }
    int ans=0;
    for(int i=1;i<N;i++){
        for(int j=0;j<g[i].size();j++){
            for(int k=0;k<j;k++){
                int a=g[i][j],b=g[i][k];
                if(1ll*a*b%(a+b)==0) ++ans;
            }
        }
    }
    printf("%d\n",ans);
}