バッチファイルでProject Euler(25)

Problem 9


この問題は、実は手計算レベルです。直角三角形の辺の長さは表すと、

a = l(m2 - n2) b = 2lmn c = l(m2 + n2)
0 < n < m m + nは奇数 mnは互いに素。

このとき周の長さは、

a + b + c = 2lm(m + n)

よって、mm + nは500の約数で互いに素。ということは、mm + nはどちらかが1, 2, 4でどちらかが1, 5, 25, 125です。m < m + n < 2mを満たすのは、m = 4, m + n = 5しかありません。

しかし、なるべくなら一般的に解きたいところです。
まず、500の約数を求めます。約数は素因数分解して出すのが正統な方法ですが、500程度ならその必要はないでしょう。2から順番に割っていき、自乗して500を超えたらそこで終わりです。これを2回してlmm + nに割り当てて、条件を満たすかを調べます。

@echo off

setlocal
set /a N = 1000
set /a M = %N% / 2
call :calc_divs %M% ds%M%
set /a size = "ds%M%.size"
set /a k = 0
:loop
    set /a d1 = "ds%M%_%k%"
    set /a q1 = %M% / %d1%
    set /a exists = "ds%q1%.size"
    if %exists% == 0 (
        call :calc_divs %q1% ds%q1%
    )
    set /a size2 = "ds%q1%.size"
    set /a l = 0
    :loop2
        set /a d2 = "ds%q1%_%l%"
        set /a d3 = %q1% / %d2%
        call :is_valid_triplet %d1% %d2% %d3%
        if %ERRORLEVEL% == 1 call :print_product %d1% %d2% %d3%
        set /a l += 1
        if %l% LSS %size2% goto :loop2
    
    set /a k += 1
    if %k% LSS %size% goto :loop
exit /b 0

:calc_divs
    set /a d = 1
    :loop_calc_divs
        set /a q = %1 / %d%
        if %q% LSS %d% exit /b 0
        set /a r = %1 %% %d%
        if %r% == 0 (
            if %q% NEQ %d% (
                call :push_vector %2 %d%
                call :push_vector %2 %q%
            ) else (
                call :push_vector %2 %d%
            )
        )
        set /a d += 1
        goto :loop_calc_divs

:is_valid_triplet
    setlocal
    if %2 GEQ %3 exit /b 0
    set /a n = %3 - %2
    if %2 LEQ %n% exit /b 0
    set /a r = %3 %% 2
    if %r% == 0 exit /b 0
    call :gcd %2 %n%
    if %ERRORLEVEL% NEQ 1 exit /b 0
    exit /b 1

:print_product
    setlocal
    set /a n = %3 - %2
    set /a a = %1 * (%2 * %2 - %n% * %n%)
    set /a b = 2 * %1 * %2 * %n%
    set /a c = %1 * (%2 * %2 + %n% * %n%)
    set /a p = %a% * %b% * %c%
    echo %p%
    exit /b 0

:gcd
    setlocal
    set /a r = %1 %% %2
    if %r% == 0 exit /b %2
    call :gcd %2 %r%
    exit /b %ERRORLEVEL%

:push_vector
    set /a _size = "%1.size"
    set /a %1_%_size% = %2
    set /a %1.size += 1
    exit /b 0

:print_vector
    setlocal
    set vector=%1
    set /a size = "%vector%.size"
    if %size% == 0 echo %2 & exit /b 0
    set /a e = "%vector%_0"
    set s=%e%
    set /a k = 1
    :loop_print_vector
        if %k% == %size% echo %s% & exit /b 0
        set /a e = "%vector%_%k%"
        set s=%s% %e%
        set /a k += 1
        goto :loop_print_vector