結果

問題 No.187 中華風 (Hard)
ユーザー authns_kyoproauthns_kyopro
提出日時 2021-02-28 23:46:01
言語 Fortran
(gFortran 13.2.0)
結果
WA  
実行時間 -
コード長 3,838 bytes
コンパイル時間 1,598 ms
コンパイル使用メモリ 36,668 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-03 00:24:42
合計ジャッジ時間 4,798 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 144 ms
5,248 KB
testcase_03 AC 148 ms
5,248 KB
testcase_04 AC 195 ms
5,248 KB
testcase_05 AC 190 ms
5,248 KB
testcase_06 AC 188 ms
5,248 KB
testcase_07 AC 192 ms
5,248 KB
testcase_08 AC 131 ms
5,248 KB
testcase_09 AC 131 ms
5,248 KB
testcase_10 AC 131 ms
5,248 KB
testcase_11 AC 191 ms
5,248 KB
testcase_12 AC 190 ms
5,248 KB
testcase_13 AC 45 ms
5,248 KB
testcase_14 AC 41 ms
5,248 KB
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 1 ms
5,248 KB
testcase_18 AC 1 ms
5,248 KB
testcase_19 AC 1 ms
5,248 KB
testcase_20 AC 128 ms
5,248 KB
testcase_21 AC 1 ms
5,248 KB
testcase_22 AC 170 ms
5,248 KB
testcase_23 AC 1 ms
5,248 KB
testcase_24 AC 1 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

module math_mod
    ! This module include
    ! gcd, lcm
    ! extgcd
    use,intrinsic :: iso_fortran_env
    implicit none
    integer(int32),parameter:: byte = int64
contains
    function lcm(a, b) result(ret)
        integer(byte),intent(in):: a,b
        integer(byte):: ret

        ret = a*b/gcd(a,b)
    end function


    recursive function gcd(a, b) result(ret)
        integer(byte),intent(in):: a,b
        integer(byte):: ret

        if (b == 0) then
            ret = a
        else
            ret = gcd(b,mod(a,b))
        end if
    end function


    recursive function extgcd(a, b, x, y) result(ret)
        ! solve:: ax + by = gcd(a,b) 
        ! input:: a, b
        ! output::  x, y, gcd(a,b)
        integer(byte),value:: a,b
        integer(byte),intent(out):: x,y
        integer(byte):: ret ! gcd(a,b)

        if (b==0_byte) then
            ret = a
            x = 1_byte
            y = 0_byte
        else
            ret = extgcd(b, mod(a,b), y, x)
            y = y - a/b * x
        end if
    end function

    recursive function mod_inv(a,m) result(ret)
        ! solve:: mod(ax, m) = 1
        !      => ax + my = 1
        ! input:: a,m
        ! output:: x <- モジュラ逆数
        integer(byte),intent(in):: a,m
        integer(byte):: ret, gcd_ma, x, y

        gcd_ma = extgcd(a,m,x,y)
        
        if (gcd_ma /= 1_byte) then
            ret = -1_byte
        else
            ret = modulo(x,m)
        end if
    end function


    function chineserem(input_b,input_m,md) result(ret)
        ! solve:: mod(b_1*k_1, m_1) = x
        !          :
        !         mod(b_n*k_n, m_n) = x を満たす最小のx
        ! input:: b(1:n), m(1:n)
        ! output:: x%md
        integer(byte):: input_b(:),input_m(:),md
        integer(byte), allocatable:: b(:), m(:), x0(:), mmul(:)
        integer(byte):: ret, i, j, g, gi, gj
        integer(byte):: t

        allocate(b(size(input_b)), source=input_b)
        allocate(m(size(input_m)), source=input_m)
        do i=1_byte,size(b)
            do j=1_byte, i-1_byte
                g = gcd(m(i),m(j))
                if (mod(b(i)-b(j), g) /= 0_byte) then
                    ret = -1_byte
                    return
                end if
                m(i) = m(i) / g
                m(j) = m(j) / g
                gi = gcd(m(i),g)
                gj = g/gi
                do while(g /= 1)
                    g = gcd(gi,gj)
                    gi = gi*g
                    gj = gj/g
                end do
                m(i) = m(i)*gi
                m(j) = m(j)*gj
                b(i) = mod(b(i), m(i))
                b(j) = mod(b(j), m(j))
                ! print'(*(i0,1x))', i, j, m(i), m(j), b(i), b(j)
            end do
        end do

        ! print*, "b", b(:)
        ! print*, "m", m(:)
        m = [m,md]
        allocate(x0(size(m)), source=0_byte)
        allocate(mmul(size(m)), source=1_byte)

        
        do i=1_byte,size(b)
            t = modulo((b(i)-x0(i)) * mod_inv(mmul(i), m(i)), m(i))
            do j=i+1,size(m)
                x0(j) = modulo(x0(j) + t * mmul(j), m(j))
                mmul(j) = modulo(mmul(j)*m(i), m(j))
            end do
        end do
        ! print*, x, mmul
        ret = modulo(x0(size(x0)), md)
    end function
end module

program main
    use,intrinsic :: iso_fortran_env
    use math_mod
    implicit none
    integer(int64):: n, i, md=10_int64**9+7, lcmv, sumx
    integer(int64),allocatable:: x(:), y(:)
    read*, n
    allocate(x(n), y(n))
    read*, (x(i), y(i), i=1,n)
    sumx=0
    lcmv=1
    do i=1,n
        sumx = modulo(sumx + x(i), md)
    end do
    if (sumx == 0) then
        do i=1,n
            lcmv = modulo(lcm(lcmv,y(i)), md)
        end do
        print'(i0)', lcmv
    else
        print'(i0)', chineserem(x,y,md)
    end if
end program main
0