# 挑战程序竞赛系列（13）：2.6辗转相除法

## AOJ 0005: GCD AND LCM

public static void main(String[] args) throws IOException {
String str;
long a,b;

a = Long.parseLong(str.substring(0, str.indexOf(" ")));
b = Long.parseLong(str.substring(str.indexOf(" ")+1, str.length()));

System.out.println(gcd(a, b) + " " + lcm(a,b));

}
}

private static long gcd(long a, long b){
if (b == 0) return a;
return gcd(b, a % b);
}

private static long lcm(long a, long b) {
return a * b / gcd(a, b);
}

## POJ 2429: GCD & LCM Inverse

• 取lcm/gcd，如3，60，得到20，在20中找到所有因子，如：2*10，4*5，取因子之和最小的两个因子。
• 输出 gcd * f1 和 gcd *f2

    static class Pair{
long fir;
long sec;
}

public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
while (true){
long gcd = in.nextLong();
long lcm = in.nextLong();
if (gcd == 0 && lcm == 0) break;
map = new HashMap<>();
Pair p = solve(gcd, lcm);
System.out.println(p.fir * gcd + " " + p.sec * gcd);
}
}

private static Pair solve(long a, long b){
long c = b / a;
find(c, 26632);

int size = 0;
for (long key : map.keySet()){
size += map.get(key);
}

long[] factor = new long[size];
int k = 0;
for (long key : map.keySet()){
int cnt = map.get(key);
while ((cnt--) != 0){
factor[k++] = key;
}
}

int mask = 1 << size;
long min = Integer.MAX_VALUE;
Pair p = new Pair();
for (int i = mask - 1; i>= 0; --i){
long f1 = 1;
for (int j = 0, m = 1; j < size; ++j, m <<= 1){
if ((i & m) != 0){
f1 *= factor[j];
}
}
long f2 = c / f1;
if (f1 < f2 && (f1 + f2) < min){
p.fir = f1;
p.sec = f2;
min = f1 + f2;
}
}
return p;
}

public static long quickMul(long a, long b, long mod){
long ans = 0;
while (b != 0){
if ((b & 1) != 0){
b--;
ans = (ans + a) % mod;
}
b >>= 1;
a = (a + a) % mod;
}
return ans;
}

public static long quickPow(long a, long b, long mod){
long ans = 1;
while (b != 0){
if ((b & 1) != 0){
b--;
ans = quickMul(ans, a, mod);
}
b >>= 1;
a = quickMul(a, a, mod);
}
return ans;
}

public static boolean witness(long a, long n){
long tem = n - 1;
int j = 0;
while (tem % 2 == 0){
tem /= 2;
j++;
}
long x = quickPow(a, tem, n);
if (x == 1 || x == n - 1) return true;

while ((j--) != 0){
x = quickMul(x, x, n);
if (x == n - 1) return true;
}
return false;
}

private static long random(long n){
return Math.abs(new Random().nextLong() % (n + 1));
}

public static boolean millerRabin(long n, int times){
if (n == 2) return true;
if (n < 2 || n % 2 == 0) return false;

for (int i = 0; i < times; ++i){
long a = random(n - 2) + 1;
if (!witness(a, n)) return false;
}
return true;
}

public static long gcd(long a, long b){
if (b == 0) return a;
else return gcd(b, a % b);
}

public static long pollardRho(long n, long c){
long x, y, d, i = 1, k = 2;
x = random(n - 1) + 1; //[1,n]
y = x;
while (true){
i++;
x = (quickMul(x, x, n) + c) % n;
d = gcd(y - x, n);
if (1 < d && d < n) return d;
if (y == x) return n;
if (i == k){
y = x;
k <<= 1;
}
}
}

static Map<Long, Integer> map;
public static void find(long n, long c){
if (n == 1) return;
if (millerRabin(n, 20)){
//map.put(n, map.getOrDefault(n, 0) + 1);
if (!map.containsKey(n)) map.put(n, 0);
map.put(n, map.get(n) + 1);
return;
}
long p = n;
long k = c;
while (p >= n) p = pollardRho(p, c--);
find(p, k);
find(n / p, k);
}

long a ，long b， long n，求：(a * b) % mod

eg:
a = a, b = 13
13  12  6  3  2  1
a   2a  4a 5a 8a 13a

1101

0110

0011

0001

1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0 = 13

public static long quickMul(long a, long b, long mod){
long ans = 0;
while (b != 0){
if ((b & 1) != 0){
b--;
ans = (ans + a) % mod;
}
b >>= 1;
a = (a + a) % mod;
}
return ans;
}

⌊xn−k⌋=⌊xn⌋−k

\lfloor \frac{x}{n} - k \rfloor = \lfloor \frac{x}{n} \rfloor - k k是整数，所以一个数在楼层之间浮动，并不影响它与地板的相对位置，很显然的一个结论，利用它就可以证明上述取模的正确性了。

public static long quickPow(long a, long b, long mod){
long ans = 1;
while (b != 0){
if ((b & 1) != 0){
b--;
ans = quickMul(ans, a, mod);
}
b >>= 1;
a = quickMul(a, a, mod);
}
return ans;
}

2/9
22/99
...
22222/99999

0.12368...

0.12 + 0.00368368...
0.123 + 0.0006868...

12/100 + 368/99900

    static class Fraction{
long fz;
long fm;

public Fraction(long fz, long fm){
long d = gcd(fz, fm);
fz /= d;
fm /= d;
this.fz = fz;
this.fm = fm;
}

long a1 = this.fz;
long b1 = this.fm;
long a2 = that.fz;
long b2 = that.fm;
return new Fraction(a1 * b2 + b1 * a2, b1 * b2);
}

public long gcd(long a, long b){
if (b == 0) return a;
else return gcd(b, a % b);
}

@Override
public String toString() {
return fz + "/" + fm;
}
}

public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
while (true){
String str = in.next();
if (str.equals("0")) break;
str = str.substring(2, str.length() - 3);
char[] digit = str.toCharArray();
if (digit.length == 1 && digit[0] == '0'){
System.out.println("0/1");
continue;
}
Fraction min = new Fraction(1, Long.MAX_VALUE);
for (int i = 0; i < digit.length - 1; ++i){
long a1 = 0;
long b1 = 1;
for (int j = 0; j <= i; ++j){
a1 = a1 * 10 + digit[j] - '0';
b1 = b1 * 10;
}
Fraction f1 = new Fraction(a1, b1);
long a2 = 0;
long b2 = 0;
for (int j = i + 1; j < digit.length; ++j){
a2 = a2 * 10 + digit[j] - '0';
b2 = b2 * 10 + 9;
}
Fraction f2 = new Fraction(a2, b2 * b1);
if (f3.fm < min.fm){
min.fz = f3.fz;
min.fm = f3.fm;
}
}

long a1 = 0;
long b1 = 0;
for (int i = 0; i < digit.length; ++i){
a1 = a1 * 10 + digit[i] - '0';
b1 = b1 * 10 + 9;
}
Fraction f3 = new Fraction(a1, b1);
if (f3.fm < min.fm){
min.fz = f3.fz;
min.fm = f3.fm;
}
System.out.println(min.toString());
}
}

0 条评论