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 (mod(a,b) == 0_byte) then ret = b return end if ret = gcd(b,mod(a,b)) 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(:) integer(byte):: ret, i, j, g, gi, gj integer(byte):: x, mmul allocate(b(0:size(input_b)), source=[0_byte, input_b]) allocate(m(0:size(input_m)), source=[1_byte, input_m]) do i=1_byte,size(b)-1_byte do j=i+1_byte,size(b)-1_byte g = gcd(m(i),m(j)) ! print'(*(i0,1x))', i,j,b(i),b(j),b(i)-b(j),g 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 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(:) mmul = 1_byte x = 0_byte do i=1_byte,size(b)-1_byte x = x + modulo((b(i)-x) * mod_inv(mmul,m(i)), m(i)) * mmul mmul = mmul*m(i) ! print*, i, x, mmul end do ! print*, x, mmul ret = x 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 integer(int64),allocatable:: x(:), y(:) read*, n allocate(x(n), y(n)) read*, (x(i), y(i), i=1,n) print*, modulo(chineserem(x,y,md), md) end program main