33 lines
772 B
Text
33 lines
772 B
Text
#include "gcd.bas"
|
|
function mul_inv( a as integer, b as integer ) as integer
|
|
if b = 1 then return 1
|
|
for i as integer = 1 to b
|
|
if a*i mod b = 1 then return i
|
|
next i
|
|
return 0
|
|
end function
|
|
|
|
function chinese_remainder(n() as integer, a() as integer) as integer
|
|
dim as integer p, i, prod = 1, sum = 0, ln = ubound(n)
|
|
for p = 0 to ln-1
|
|
for i = p+1 to ln
|
|
if gcd(n(i), n(p))>1 then
|
|
print "N not coprime"
|
|
end
|
|
end if
|
|
next i
|
|
next p
|
|
for i = 0 to ln
|
|
prod *= n(i)
|
|
next i
|
|
for i = 0 to ln
|
|
p = prod/n(i)
|
|
sum += a(i) * mul_inv(p, n(i))*p
|
|
next i
|
|
return sum mod prod
|
|
end function
|
|
|
|
dim as integer n(0 to 2) = { 3, 5, 7 }
|
|
dim as integer a(0 to 2) = { 2, 3, 2 }
|
|
|
|
print chinese_remainder(n(), a())
|