1 #include <iostream> 2 using namespace std; 3 const int MAXN = 10010; 4 5 struct bign 6 { 7 int len,s[MAXN]; 8 bign() 9 { 10 memset(s,0,sizeof(s)); 11 len=1; 12 } 13 bign (int num) { *this=num; } 14 bign (const char *num) { *this=num; } 15 //--------------------------------------- 16 bign operator = (const int num) 17 { 18 char s[MAXN]; 19 sprintf(s, "%d", num); 20 *this = s; 21 return *this; 22 } 23 bign operator = (const char *num) 24 { 25 for(int i = 0; num[i] == '0'; num++) ; 26 len = strlen(num); 27 for(int i = 0; i < len; i++) s[i] = num[len-i-1] - '0'; 28 return *this; 29 } 30 //--------------------------------------- 31 bign operator + (const bign &b) const //+ 32 { 33 bign c; 34 c.len = 0; 35 for(int i = 0, g = 0; g || i < max(len, b.len); i++) 36 { 37 int x = g; 38 if(i < len) x += s[i]; 39 if(i < b.len) x += b.s[i]; 40 c.s[c.len++] = x % 10; 41 g = x / 10; 42 } 43 return c; 44 } 45 bign operator += (const bign &b) 46 { 47 *this = *this + b; 48 return *this; 49 } 50 //--------------------------------------- 51 void clean() 52 { 53 while(len > 1 && !s[len-1]) len--; 54 } 55 //--------------------------------------- 56 bign operator * (const bign &b) //* 57 { 58 bign c; 59 c.len = len + b.len; 60 for(int i = 0; i < len; i++) 61 { 62 for(int j = 0; j < b.len; j++) 63 { 64 c.s[i+j] += s[i] * b.s[j]; 65 } 66 } 67 for(int i = 0; i < c.len; i++) 68 { 69 c.s[i+1] += c.s[i]/10; 70 c.s[i] %= 10; 71 } 72 c.clean(); 73 return c; 74 } 75 bign operator *= (const bign &b) 76 { 77 *this = *this * b; 78 return *this; 79 } 80 //--------------------------------------- 81 bign operator - (const bign &b) 82 { 83 bign c; 84 c.len = 0; 85 for(int i = 0, g = 0; i < len; i++) 86 { 87 int x = s[i] - g; 88 if(i < b.len) x -= b.s[i]; 89 if(x >= 0) g = 0; 90 else 91 { 92 g = 1; 93 x += 10; 94 } 95 c.s[c.len++] = x; 96 } 97 c.clean(); 98 return c; 99 } 100 bign operator -= (const bign &b) 101 { 102 *this = *this - b; 103 return *this; 104 } 105 //--------------------------------------- 106 bign operator / (const bign &b) 107 { 108 bign c, f = 0; 109 for(int i = len-1; i >= 0; i--) 110 { 111 f = f*10; 112 f.s[0] = s[i]; 113 while(f >= b) 114 { 115 f -= b; 116 c.s[i]++; 117 } 118 } 119 c.len = len; 120 c.clean(); 121 return c; 122 } 123 bign operator /= (const bign &b) 124 { 125 *this = *this / b; 126 return *this; 127 } 128 //--------------------------------------- 129 bign operator % (const bign &b) 130 { 131 bign r = *this / b; 132 r = *this - r*b; 133 return r; 134 } 135 bign operator %= (const bign &b) 136 { 137 *this = *this % b; 138 return *this; 139 } 140 //--------------------------------------- 141 bool operator < (const bign &b) 142 { 143 if(len != b.len) return len < b.len; 144 for(int i = len-1; i >= 0; i--) 145 { 146 if(s[i] != b.s[i]) return s[i] < b.s[i]; 147 } 148 return false; 149 } 150 bool operator > (const bign &b) 151 { 152 if(len != b.len) return len > b.len; 153 for(int i = len-1; i >= 0; i--) 154 { 155 if(s[i] != b.s[i]) return s[i] > b.s[i]; 156 } 157 return false; 158 } 159 bool operator == (const bign &b) 160 { 161 return !(*this > b) && !(*this < b); 162 } 163 bool operator != (const bign &b) 164 { 165 return !(*this == b); 166 } 167 bool operator <= (const bign &b) 168 { 169 return *this < b || *this == b; 170 } 171 bool operator >= (const bign &b) 172 { 173 return *this > b || *this == b; 174 } 175 //--------------------------------------- 176 string str() const 177 { 178 string res = ""; 179 for(int i = 0; i < len; i++) res = char(s[i]+'0') + res; 180 return res; 181 } 182 }; 183 //--------------------------------------- 184 istream& operator >> (istream &in, bign &x) 185 { 186 string s; 187 in >> s; 188 x = s.c_str(); 189 return in; 190 } 191 192 ostream& operator << (ostream &out, const bign &x) 193 { 194 out << x.str(); 195 return out; 196 } 197 //--------------------------------------- 198 199 bign gcd(bign a,bign b) 200 { 201 if(a==0) return b; 202 return gcd(b%a,a); 203 } 204 int main() 205 { 206 bign a,b,temp,ans; 207 cin>>a>>b; 208 cout<<a/b<<endl; 209 cout<<a%b; 210 return 0; 211 }