1 #pragma comment(linker,"/STACK:36777216")  2 #include<cstdio>  3 #include<cstdlib>  4 #include<cstring>  5 #include<iostream>  6 #include<algorithm>  7 #include<cmath>  8 #include<string>  9 #include<stack> 10 #include<queue> 11 #include<vector> 12 #include<list> 13 #include<map> 14 #include<set> 15 #include<deque> 16 #include<ctime> 17 #include<cassert> 18 #include<limits> 19 #include<fstream> 20 #include<functional> 21 #include<numeric> 22 #include<iomanip> 23 #include<utility> 24 #include<complex> 25 //#include<bits/stdc++.h> 26 #define INF 0x0ffffff 27 #define EPS 1e-9 28 #define PI acos(-1.0) 29 #define E exp(1.0) 30 using namespace std; 31  32 #ifdef _int64 33  typedef _int64 LL; 34 #else 35  typedef long long LL; 36 #endif 37  38 inline int compare(string str1, string str2) 39 { 40       if(str1.size() > str2.size()) 41             return 1; 42       else if(str1.size() < str2.size()) 43             return -1; 44       else 45             return str1.compare(str2); 46 } 47  48  49 string ADD_INT(string str1, string str2) 50 { 51       string MINUS_INT(string str1, string str2); 52       int sign = 1; 53       string str; 54       if(str1[0] == ‘-‘) { 55            if(str2[0] == ‘-‘) { 56                  sign = -1; 57                  str = ADD_INT(str1.erase(0, 1), str2.erase(0, 1)); 58            }else { 59                  str = MINUS_INT(str2, str1.erase(0, 1)); 60            } 61       }else { 62            if(str2[0] == ‘-‘) 63                  str = MINUS_INT(str1, str2.erase(0, 1)); 64            else { 65                  string::size_type l1, l2; 66                  int i; 67                  l1 = str1.size(); l2 = str2.size(); 68                  if(l1 < l2) { 69                        for(i = 1; i <= l2 - l1; i++) 70                        str1 = "0" + str1; 71                  }else { 72                        for(i = 1; i <= l1 - l2; i++) 73                        str2 = "0" + str2; 74                  } 75                  int int1 = 0, int2 = 0; 76                  for(i = str1.size() - 1; i >= 0; i--) { 77                        int1 = (int(str1[i]) - 48 + int(str2[i]) - 48 + int2) % 10; 78                        int2 = (int(str1[i]) - 48 + int(str2[i]) - 48 +int2) / 10; 79                        str = char(int1 + 48) + str; 80                  } 81                  if(int2 != 0) str = char(int2 + 48) + str; 82           } 83      } 84  85      if((sign == -1) && (str[0] != ‘0‘)) 86           str = "-" + str; 87      return str; 88 } 89  90  91  92 string MINUS_INT(string str1, string str2) 93 { 94      string MULTIPLY_INT(string str1, string str2); 95      int sign = 1; 96      string str; 97      if(str2[0] == ‘-‘) 98             str = ADD_INT(str1, str2.erase(0, 1)); 99      else {100             int res = compare(str1, str2);101             if(res == 0) return "0";102             if(res < 0) {103                   sign = -1;104                   string temp = str1;105                   str1 = str2;106                   str2 = temp;107             }108             string::size_type tempint;109             tempint = str1.size() - str2.size();110             for(int i = str2.size() - 1; i >= 0; i--) {111                  if(str1[i + tempint] < str2[i]) {112                        str1[i + tempint - 1] = char(int(str1[i + tempint - 1]) - 1);113                        str = char(str1[i + tempint] - str2[i] + 58) + str;114                  }115                  else116                        str = char(str1[i + tempint] - str2[i] + 48) + str;117             }118            for(int i = tempint - 1; i >= 0; i--)119                 str = str1[i] + str;120      }121 122      str.erase(0, str.find_first_not_of(‘0‘));123      if(str.empty()) str = "0";124      if((sign == -1) && (str[0] != ‘0‘))125           str = "-" + str;126      return str;127 }128 129 130 string MULTIPLY_INT(string str1, string str2)131 {132      int sign = 1;133      string str;134      if(str1[0] == ‘-‘) {135            sign *= -1;136            str1 = str1.erase(0, 1);137      }138      if(str2[0] == ‘-‘) {139            sign *= -1;140            str2 = str2.erase(0, 1);141      }142      int i, j;143      string::size_type l1, l2;144      l1 = str1.size(); l2 = str2.size();145      for(i = l2 - 1; i >= 0; i --) {146            string tempstr;147            int int1 = 0, int2 = 0, int3 = int(str2[i]) - 48;148            if(int3 != 0) {149                   for(j = 1; j <= (int)(l2 - 1 - i); j++)150                         tempstr = "0" + tempstr;151                   for(j = l1 - 1; j >= 0; j--) {152                         int1 = (int3 * (int(str1[j]) - 48) + int2) % 10;153                         int2 = (int3 * (int(str1[j]) - 48) + int2) / 10;154                         tempstr = char(int1 + 48) + tempstr;155                   }156                   if(int2 != 0) tempstr = char(int2 + 48) + tempstr;157            }158            str = ADD_INT(str, tempstr);159      }160 161      str.erase(0, str.find_first_not_of(‘0‘));162      if(str.empty()) str = "0";163      if((sign == -1) && (str[0] != ‘0‘))164            str = "-" + str;165      return str;166 }167 168 string DIVIDE_INT(string str1, string str2, int flag)169 {170 171      string quotient, residue;172      int sign1 = 1, sign2 = 1;173      if(str2 == "0") {174            quotient = "ERROR!";175            residue = "ERROR!";176            if(flag == 1) return quotient;177            else return residue;178      }179      if(str1 == "0") {180            quotient = "0";181            residue = "0";182      }183      if(str1[0] == ‘-‘) {184            str1 = str1.erase(0, 1);185            sign1 *= -1;186            sign2 = -1;187      }188      if(str2[0] == ‘-‘) {189            str2 = str2.erase(0, 1);190            sign1 *= -1;191      }192      int res = compare(str1, str2);193      if(res < 0) {194            quotient = "0";195            residue = str1;196      }else if(res == 0) {197            quotient = "1";198            residue = "0";199      }else {200            string::size_type l1, l2;201            l1 = str1.size(); l2 = str2.size();202            string tempstr;203            tempstr.append(str1, 0, l2 - 1);204 205            for(int i = l2 - 1; i < l1; i++) {206                  tempstr = tempstr + str1[i];207                  for(char ch = ‘9‘; ch >= ‘0‘; ch --) {208                        string str;209                        str = str + ch;210                        if(compare(MULTIPLY_INT(str2, str), tempstr) <= 0) {211                               quotient = quotient + ch;212                               tempstr = MINUS_INT(tempstr, MULTIPLY_INT(str2, str));213                               break;214                        }215                  }216            }217            residue = tempstr;218      }219 220      quotient.erase(0, quotient.find_first_not_of(‘0‘));221      if(quotient.empty()) quotient = "0";222      if((sign1 == -1) && (quotient[0] != ‘0‘))223      quotient = "-" + quotient;224      if((sign2 == -1) && (residue[0] != ‘0‘))225      residue = "-" + residue;226      if(flag == 1) return quotient;227      else return residue;228 }229 230 231 232 233 string operator %(string str1,string str2)234 {235     return DIVIDE_INT(str1, str2, 0);236 }237 238 239 bool operator ==(string str,int num)240 {241     if(str.size()==1&&str[0]-‘0‘==num)242         return 1;243     return 0;244 }245 246 string gcd(string a,string b){247     if(a==0) return b;248     return gcd(b%a,a);249     }250 251 252 string shift(string str,int oldb,int newb)253 {254     string ans;255     char t[10000],A[10000],d[10000];256     int k,i,l;257     const char *a=str.data();258     for(k=i=strlen(a); 0<i--;)t[k-1-i]=a[i]-(a[i]<58?48:a[i]<97?55:61);259         for(l=0; k;) {260             for(i=k; 1<i--;) {261                 t[i-1]+=t[i]%newb*oldb;262                 t[i]/=newb;263             }264             A[l++]=t[0]%newb;265             t[0]/=newb;266             for(; 0<k&&!t[k-1]; k--);267         }268         for(d[l]=i=0; i<l; i++)d[l-1-i]=A[i]+(A[i]<10?48:A[i]<36?55:61);269         ans=d;270         return ans;271 }272 273 274 int main()275 {276 //freopen("in.txt","r",stdin);277 //freopen("out.txt","w",stdout);278 int t;279 cin>>t;280 int kase=1;281 while(t--)282 {283     string h,w;284     cin>>h>>w;285     string h_=shift(h,2,10);286     string w_=shift(w,2,10);287     string ans_=gcd(h_,w_);288     string ans=shift(ans_,10,2);289     cout<<"Case #"<<kase<<": ";290     //printf("Case #%d: ",kase);291     cout<<ans<<endl;292     ++kase;293 }294 return 0;295 }