HDU 5050 Divided Land 2014 ACM/ICPC Asia Regional Shanghai Online
來源：程序員人生 發布時間：2014-10-02 08:00:01 閱讀次數：3044次
求2個二進制數的GCD
java大數+位壓
import java.math.*;
import java.util.*;
import java.io.*;
public class Main {
public BigInteger GCD(BigInteger x, BigInteger y) {
if(x.compareTo(y) < 0) {
BigInteger tmp = x;
x = y;
y = tmp;
}
while(y.compareTo(BigInteger.ZERO) != 0) {
BigInteger tmp = x.mod(y);
x = y;
y = tmp;
}
return x;
}
public void work() {
int T, cas = 0;
String a = new String();
String b = new String();
char c[] = new char[1005];
T = cin.nextInt();
while (T-- > 0) {
a = cin.next();
b = cin.next();
BigInteger x = BigInteger.ZERO;
for(int i = 0; i < a.length(); i ++) {
x = x.multiply(BigInteger.valueOf(2));
if(a.charAt(i) == '1') x = x.add(BigInteger.ONE);
}
BigInteger y = BigInteger.ZERO;
for(int i = 0; i < b.length(); i ++) {
y = y.multiply(BigInteger.valueOf(2));
if(b.charAt(i) == '1') y = y.add(BigInteger.ONE);
}
// System.out.println(x + "," + y);
x = GCD(x, y);
int i = 0;
while(x.compareTo(BigInteger.ZERO) > 0) {
if( x.mod(BigInteger.valueOf(2)).compareTo(BigInteger.ZERO) == 0) {
c[i] = '0';
} else c[i] = '1';
i ++;
x = x.divide(BigInteger.valueOf(2));
}
cas ++;
System.out.print("Case #" + cas + ": ");
while(i > 0) {
System.out.print(c[i-1]);
i--;
}
System.out.println();
}
}
Main() {
cin = new Scanner(System.in);
}
public static void main(String[] args) {
Main e = new Main();
e.work();
}
public Scanner cin;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
