国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > 互联网 > hdu5050_2014ACM上海__Divided Land

hdu5050_2014ACM上海__Divided Land

来源:程序员人生   发布时间:2014-10-08 08:00:01 阅读次数:2901次

本文出自:点击打开链接


原题见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; }


生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生