本文出自：点击打开链接
原题见hdu5050
代码：
#include #include #include #include #include #include #include #include #include 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\n", (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 &x, const bitset &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 gcd(bitset u, bitset v) { bitset one (string("1")); bitset 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 , allocator >(); string t2 = v.to_string , allocator >(); if (t1 > t2) { bitset 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; }