バッチファイルでProject Euler（60）

Problem 26

pが素数なら

10^d ≡ 1 (mod p)

となる最小のdがサイクル長となります。実質的には、大きいほうから試してdがn-1となる素数pを探せばよいでしょう。フェルマーの小定理からn-1では必ず上の式を満たします。また、これから上の式を満たすdはn-1の約数となることがわかります。よって、n-1以外のすべてのdが上の式を満たさなければよいことになります。

@echo off

setlocal
set /a N = 1000
set /a m = %N% - 1
:loop
    call :is_prime %m%
    if %ERRORLEVEL% == 0 (
        set /a m -= 1
        goto :loop
    )
    call :is_valid %m%
    if %ERRORLEVEL% == 0 (
        set /a m -= 1
        goto :loop
    )
echo %m%
exit /b 0

:is_prime
    setlocal
    set /a p = 2
    :loop_is_prime
        set /a p_sq = %p% * %p%
        if %p_sq% GTR %1 exit /b 1
        set /a r = %1 %% %p%
        if %r% == 0 exit /b 0
        set /a p += 1
        goto :loop_is_prime

:is_valid
    setlocal
    set /a m = %1 - 1
    set /a d = 2
    :loop_is_valid
        set /a d_sq = %d% * %d%
        if %d_sq% GTR %m% exit /b 1
        set /a r = %m% %% %d%
        if %r% NEQ 0 (
            set /a d += 1
            goto :loop_is_valid
        )
        call :pow 10 %d% %1
        if %ERRORLEVEL% == 1 exit /b 0
        set /a d2 = %1 / %d%
        call :pow 10 %d2% %1
        if %ERRORLEVEL% == 1 exit /b 0
        set /a d += 1
        goto :loop_is_valid

:pow
    setlocal
    if %2 == 0 exit /b 1
    
    set /a half_e = %2 / 2
    call :pow %1 %half_e% %3
    set /a m = %ERRORLEVEL% * %ERRORLEVEL% %% %3
    set /a r_e = %2 %% 2
    if %r_e% == 1 set /a m = %m% * %1 %% %3
    exit /b %m%