也是很赤裸裸的模型，這里求的是絕對值最小解，還有就是用到高精。我用java不會寫傳引用，因此只好開了全局變量。
import java.math.*;
import java.util.*;
public class Main
{
static public BigInteger x = null, y = null;
static BigInteger extended_gcd(BigInteger a, BigInteger b)
{
BigInteger zero = new BigInteger(new String("0"));
BigInteger ret, tmp;
if (b.compareTo(zero) == 0)
{
x = new BigInteger(new String("1"));
y = zero;
return a;
}
ret = extended_gcd(b, a.mod(b));
tmp = x;
x = y;
y = tmp.subtract(a.divide(b).multiply(y));
return ret;
}
static BigInteger modular_linear_equation(BigInteger a, BigInteger b, BigInteger n)
{
BigInteger e, e2;
BigInteger d = extended_gcd(a, n);
e = b.divide(d).multiply(x).mod(n.divide(d));
e2 = e.subtract(n.divide(d)).abs();
if (e.compareTo(e2) < 0) return e;
return e2;
}
public static void main(String[] args)
{
BigInteger a, b, c;
Scanner in = new Scanner(System.in);
while (in.hasNext())
{
a = in.nextBigInteger();
b = in.nextBigInteger();
c = in.nextBigInteger();
c = c.multiply(new BigInteger(new String("-1")));
System.out.println(modular_linear_equation(a, c, b));
}
}
}posted on 2009-03-17 20:16
sdfond 閱讀(185)
評論(0) 編輯 收藏 引用 所屬分類:
Algorithm - Number Theory