本文出自：点击打开链接
原题见hdu5050
代码：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long int
#define ui unsigned long
#define ull unsigned long long
#define MEM(a) memset(a, 0, sizeof(a))
#define MEMM(a) memset(b, -1, sizeof(b))
#define DBG(x, n) cout << (x) << " " << (n) << endl;
#define SL(a) strlen(a)
#define RS(s) scanf("%s", (s))
#define PI(r) printf("%d
", (r))
#define RI(a) scanf("%d", &(a))
#define RII(a, b) scanf("%d%d", &(a), &(b))
#define RIII(a, b, c) scanf("%d%d%d", &(a), &(b), &(c))
#ifdef ONLINE_JUDGE
#define FOI(file) 0
#define FOW(file) 0
#else
#define FOI(file) freopen(file,"r",stdin);
#define FOW(file) freopen(file,"w",stdout);
#endif
#define N 1001
bitset <1001> w;
bitset <1001> h;
bitset <1001> d;
void bitsetSubtract(bitset<N> &x, const bitset<N> &y) {
bool borrow = false;
for (int i = 0; i < N; i++) {
if (borrow) {
if (x[i]) {
x[i] = y[i];
borrow = y[i];
} else {
x[i] = !y[i];
borrow = true;
}
} else {
if (x[i]) {
x[i] = !y[i];
borrow = false;
} else {
x[i] = y[i];
borrow = y[i];
}
}
}
}
bitset<N> gcd(bitset<N> u, bitset<N> v) {
bitset<N> one (string("1"));
bitset<N> zero (string("0"));
int shift;
if (u == 0) return v;
if (v == 0) return u;
for (shift = 0; ((u | v) & one) == zero; ++shift) {
u >>= 1;
v >>= 1;
}
while ((u & one) == zero) u >>= 1;
do {
while ((v & one) == zero) v >>= 1;
string t1 = u.to_string<char, char_traits<char>, allocator<char> >();
string t2 = v.to_string<char, char_traits<char>, allocator<char> >();
if (t1 > t2) {
bitset<N> t = v;
v = u;
u = t;
}
bitsetSubtract(v,u);
} while (v != 0);
return u << shift;
}
int main()
{
//FOI("input");
//FOW("output");
//write your programme here
int t;
scanf("%d", &t);
int i;
int j;
for(i = 1; i <= t; i++)
{
cin >> w >> h;
d = gcd(w, h);
printf("Case #%d: ", i);
// cout << d << endl;
j = 1000;
while(d[j] != 1)
j--;
while(j != -1)
{
cout << d[j];
j --;
}
cout << endl;
}
return 0;
}