API tools faq
paste
Advertisement
Rapptz

:|

Rapptz
Jan 13th, 2013
293
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
HTML 91.63 KB | None | 0 0
raw download clone embed print report
  1.  
  2. <!DOCTYPE html><html><head><meta charset="UTF-8"><style>
  3. html {
  4.     font-size: 100%;
  5.     overflow-y: scroll;
  6.     -webkit-text-size-adjust: 100%;
  7.     -ms-text-size-adjust: 100%;
  8. }
  9. body {
  10.     color: #444;
  11.     font-family: Georgia, Palatino, 'Palatino Linotype', Times, 'Times New Roman', serif, "Hiragino Sans GB", "STXihei", "微软雅黑";
  12.     font-size: 12px;
  13.     line-height: 1.5em;
  14.     background: #fefefe;
  15.     width: 45em;
  16.     margin: 10px auto;
  17.     padding: 1em;
  18.     outline: 1300px solid #FAFAFA;
  19. }
  20. a {
  21.     color: #0645ad;
  22.     text-decoration: none;
  23. }
  24. a:visited { color: #0b0080 }
  25. a:hover { color: #06e }
  26. a:active { color: #faa700 }
  27. a:focus { outline: thin dotted }
  28. a:hover, a:active { outline: 0 }
  29. span.backtick {
  30.     border: 1px solid #EAEAEA;
  31.     border-radius: 3px;
  32.     background: #F8F8F8;
  33.     padding: 0 3px 0 3px;
  34. }
  35. ::-moz-selection {
  36.     background: rgba(255,255,0,0.3);
  37.     color: #000;
  38. }
  39. ::selection {
  40.     background: rgba(255,255,0,0.3);
  41.     color: #000;
  42. }
  43. a::-moz-selection {
  44.     background: rgba(255,255,0,0.3);
  45.     color: #0645ad;
  46. }
  47. a::selection {
  48.     background: rgba(255,255,0,0.3);
  49.     color: #0645ad;
  50. }
  51. p { margin: 1em 0 }
  52. img { max-width: 100% }
  53. h1, h2, h3, h4, h5, h6 {
  54.     font-weight: normal;
  55.     color: #111;
  56.     line-height: 1em;
  57. }
  58. h4, h5, h6 { font-weight: bold }
  59. h1 { font-size: 2.5em }
  60. h2 {
  61.     font-size: 2em;
  62.     border-bottom: 1px solid silver;
  63.     padding-bottom: 5px;
  64. }
  65. h3 { font-size: 1.5em }
  66. h4 { font-size: 1.2em }
  67. h5 { font-size: 1em }
  68. h6 { font-size: 0.9em }
  69. blockquote {
  70.     color: #666666;
  71.     margin: 0;
  72.     padding-left: 3em;
  73.     border-left: 0.5em #EEE solid;
  74. }
  75. hr {
  76.     display: block;
  77.     height: 2px;
  78.     border: 0;
  79.     border-top: 1px solid #aaa;
  80.     border-bottom: 1px solid #eee;
  81.     margin: 1em 0;
  82.     padding: 0;
  83. }
  84. kbd, samp {
  85.     color: #000;
  86.     font-family: monospace;
  87.     font-size: 0.88em;
  88.     border-radius: 3px;
  89.     background-color: #F8F8F8;
  90.     border: 1px solid #CCC;
  91. }
  92. code, tt {
  93.   margin: 0 2px;
  94.   padding: 0 5px;
  95.   white-space: nowrap;
  96.   font-family: Consolas, Monaco, monospace;
  97.   border: 1px solid #eaeaea;
  98.   background-color: #f8f8f8;
  99.   border-radius: 3px; }
  100.  
  101. pre code {
  102.   margin: 0;
  103.   padding: 0;
  104.   white-space: pre;
  105.   border: none;
  106.   background: transparent; }
  107.  
  108. .highlight pre {
  109.   background-color: #f8f8f8;
  110.   border: 1px solid #cccccc;
  111.   font-family: Consolas, Monaco, monospace;
  112.   font-size: 13px;
  113.   line-height: 19px;
  114.   overflow: auto;
  115.   padding: 6px 10px;
  116.   border-radius: 3px; }
  117.  
  118. pre {
  119.   background-color: #f8f8f8;
  120.   border: 1px solid #cccccc;
  121.   font-size: 13px;
  122.   line-height: 19px;
  123.   overflow: auto;
  124.   padding: 6px 10px;
  125.   border-radius: 3px; }
  126.   pre code, pre tt {
  127.     background-color: transparent;
  128.     border: none; }
  129.  
  130.  
  131. .markdown-body code,.markdown-body tt{margin:0 2px;padding:0px 5px;white-space:nowrap;border:1px solid #eaeaea;background-color:#f8f8f8;border-radius:3px}
  132. .markdown-body pre>code{margin:0;padding:0;white-space:pre;border:none;background:transparent}
  133. .markdown-body .highlight pre,.markdown-body pre{background-color:#f8f8f8;border:1px solid #ccc;font-size:13px;line-height:19px;overflow:auto;padding:6px 10px;border-radius:3px}
  134. .markdown-body pre code,.markdown-body pre tt{background-color:transparent;border:none}
  135. .highlight{background:#ffffff}
  136. .highlight .c{color:#999988;font-style:italic}
  137. .highlight .err{color:#a61717;background-color:#e3d2d2}
  138. .highlight .k{color: #0000ff;}
  139. /*.highlight .o{font-weight:bold}*/
  140. .highlight .cm{color:#008000;font-style:italic}
  141. .highlight .cp{color:#d14;}
  142. .highlight .c1{color:#008000;font-style:italic}
  143. .highlight .cs{color:#999999;font-weight:bold;font-style:italic}
  144. .highlight .gd{color:#000000;background-color:#ffdddd}
  145. .highlight .gd .x{color:#000000;background-color:#ffaaaa}
  146. .highlight .ge{font-style:italic}
  147. .highlight .gr{color:#aa0000}
  148. .highlight .gh{color:#999999}
  149. .highlight .gi{color:#000000;background-color:#ddffdd}
  150. .highlight .gi .x{color:#000000;background-color:#aaffaa}
  151. .highlight .go{color:#888888}
  152. .highlight .gp{color:#555555}
  153. .highlight .gs{font-weight:bold}
  154. .highlight .gu{color:#800080;font-weight:bold}
  155. .highlight .gt{color:#aa0000}
  156. .highlight .kc{font-weight:bold}
  157. .highlight .kd{font-weight:bold}
  158. .highlight .kn{font-weight:bold}
  159. .highlight .kp{font-weight:bold}
  160. .highlight .kr{font-weight:bold}
  161. .highlight .kt{color:#0000ff;}
  162. .highlight .m{color:#009999}
  163. .highlight .s{color:#d14}
  164. .highlight .na{color:#008080}
  165. .highlight .nb{color:#0086B3}
  166. .highlight .nc{color:#445588;font-weight:bold}
  167. .highlight .no{color:#008080}
  168. .highlight .ni{color:#800080}
  169. .highlight .ne{color:#990000;font-weight:bold}
  170. .highlight .nf{color:#990000;font-weight:bold}
  171. .highlight .nn{color:#555555}
  172. .highlight .nt{color:#000080}
  173. .highlight .nv{color:#008080}
  174. .highlight .ow{font-weight:bold}
  175. .highlight .w{color:#bbbbbb}
  176. .highlight .mf{color:#009999}
  177. .highlight .mh{color:#009999}
  178. .highlight .mi{color:#009999}
  179. .highlight .mo{color:#009999}
  180. .highlight .sb{color:#d14}
  181. .highlight .sc{color:#d14}
  182. .highlight .sd{color:#d14}
  183. .highlight .s2{color:#d14}
  184. .highlight .se{color:#d14}
  185. .highlight .sh{color:#d14}
  186. .highlight .si{color:#d14}
  187. .highlight .sx{color:#d14}
  188. .highlight .sr{color:#009926}
  189. .highlight .s1{color:#d14}
  190. .highlight .ss{color:#990073}
  191. .highlight .bp{color:#999999}
  192. .highlight .vc{color:#008080}
  193. .highlight .vg{color:#008080}
  194. .highlight .vi{color:#008080}
  195. .highlight .il{color:#009999}
  196. .highlight .gc{color:#999;background-color:#EAF2F5}
  197. .type-csharp .highlight .k{color:#0000FF}
  198. .type-csharp .highlight .kt{color:#0000FF}
  199. .type-csharp .highlight .nf{color:#000000;font-weight:normal}
  200. .type-csharp .highlight .nc{color:#2B91AF}
  201. .type-csharp .highlight .nn{color:#000000}
  202. .type-csharp .highlight .s{color:#A31515}
  203. .type-csharp .highlight .sc{color:#A31515}
  204.  
  205. b, strong { font-weight: bold }
  206. dfn { font-style: italic }
  207. ins {
  208.     background: #ff9;
  209.     color: #000;
  210.     text-decoration: none;
  211. }
  212. mark {
  213.     background: #ff0;
  214.     color: #000;
  215.     font-style: italic;
  216.     font-weight: bold;
  217. }
  218. sub, sup {
  219.     font-size: 75%;
  220.     line-height: 0;
  221.     position: relative;
  222.     vertical-align: baseline;
  223. }
  224. sup { top: -0.5em }
  225. sub { bottom: -0.25em }
  226. ul, ol {
  227.     margin: 1em 0;
  228.     padding: 0 0 0 2em;
  229. }
  230. li p:last-child { margin: 0 }
  231. dd { margin: 0 0 0 2em }
  232. img {
  233.     border: 0;
  234.     -ms-interpolation-mode: bicubic;
  235.     vertical-align: middle;
  236. }
  237. table {
  238.   padding: 0; }
  239.   table tr {
  240.     border-top: 1px solid #cccccc;
  241.     background-color: white;
  242.     margin: 0;
  243.     padding: 0; }
  244.     table tr:nth-child(2n) {
  245.       background-color: #f8f8f8; }
  246.     table tr th {
  247.       font-weight: bold;
  248.       border: 1px solid #cccccc;
  249.       text-align: left;
  250.       margin: 0;
  251.       padding: 6px 13px; }
  252.     table tr td {
  253.       border: 1px solid #cccccc;
  254.       text-align: left;
  255.       margin: 0;
  256.       padding: 6px 13px; }
  257.     table tr th :first-child, table tr td :first-child {
  258.       margin-top: 0; }
  259.     table tr th :last-child, table tr td :last-child {
  260.       margin-bottom: 0;
  261.     }
  262.  
  263. td { vertical-align: top }
  264. @media only screen and (min-width: 480px) {
  265.     body { font-size: 14px }
  266. }
  267. @media only screen and (min-width: 768px) {
  268.     body { font-size: 16px }
  269. }
  270. @media print {
  271.     * {
  272.         background: transparent !important;
  273.         color: black !important;
  274.         filter: none !important;
  275.         -ms-filter: none !important;
  276.     }
  277.     body {
  278.         font-size: 12pt;
  279.         max-width: 100%;
  280.     }
  281.     a, a:visited { text-decoration: underline }
  282.     hr {
  283.         height: 1px;
  284.         border: 0;
  285.         border-bottom: 1px solid black;
  286.     }
  287.     a[href]:after { content: " (" attr(href) ")" }
  288.     abbr[title]:after { content: " (" attr(title) ")" }
  289.     .ir a:after, a[href^="javascript:"]:after, a[href^="#"]:after { content: "" }
  290.     pre, blockquote {
  291.         border: 1px solid #999;
  292.         padding-right: 1em;
  293.         page-break-inside: avoid;
  294.     }
  295.     tr, img { page-break-inside: avoid }
  296.     img { max-width: 100% !important }
  297. }
  298. </style>
  299.  
  300.  
  301. <script>document.write('<script src="http://' + (location.host || 'localhost').split(':')[0] + ':35729/livereload.js?snipver=1"></' + 'script>')</script></head><body><h2>Syntax Highlighting Test</h2>
  302.  
  303. <div class="highlight"><pre><span class="cp">#ifndef GEARS_BIG_INTEGER_HPP</span>
  304. <span class="cp">#define GEARS_BIG_INTEGER_HPP</span>
  305.  
  306. <span class="c1">//Includes</span>
  307. <span class="cp">#include &lt;algorithm&gt;</span>
  308. <span class="cp">#include &lt;iterator&gt;</span>
  309. <span class="cp">#include &lt;iostream&gt;</span>
  310. <span class="cp">#include &lt;sstream&gt;</span>
  311. <span class="cp">#include &lt;string&gt;</span>
  312. <span class="cp">#include &lt;deque&gt;</span>
  313. <span class="cp">#include &lt;map&gt;</span>
  314. <span class="cp">#include &lt;stdexcept&gt;</span>
  315.  
  316. <span class="cm">/*</span>
  317. <span class="cm">TODO: Organize code, possibly update to more C++11 features.</span>
  318. <span class="cm">More error checking, improve division to be more accurate.</span>
  319. <span class="cm">More mathematical functions, e.g. isPrime() and sqrt()</span>
  320. <span class="cm">*/</span>
  321.  
  322. <span class="k">namespace</span> <span class="n">gears</span> <span class="p">{</span>
  323.  
  324. <span class="k">typedef</span> <span class="kt">unsigned</span> <span class="kt">long</span> <span class="kt">long</span> <span class="n">ullong</span><span class="p">;</span>
  325.  
  326. <span class="k">struct</span> <span class="n">BigInteger</span> <span class="p">{</span>
  327.    <span class="c1">//Base value.</span>
  328.     <span class="k">static</span> <span class="k">const</span> <span class="n">ullong</span> <span class="n">base</span> <span class="o">=</span> <span class="mi">10000</span><span class="p">;</span>
  329.     <span class="c1">//N value</span>
  330.     <span class="k">static</span> <span class="k">const</span> <span class="n">ullong</span> <span class="n">N</span> <span class="o">=</span> <span class="mi">4</span><span class="p">;</span>
  331.  
  332.     <span class="c1">//Digits holder.</span>
  333.     <span class="n">std</span><span class="o">::</span><span class="n">deque</span><span class="o">&lt;</span><span class="n">ullong</span><span class="o">&gt;</span> <span class="n">digits</span><span class="p">;</span>
  334.  
  335.     <span class="c1">//Default constructors.</span>
  336.     <span class="n">BigInteger</span><span class="p">();</span>
  337.     <span class="n">BigInteger</span><span class="p">(</span><span class="n">std</span><span class="o">::</span><span class="n">string</span> <span class="n">str</span><span class="p">);</span>
  338.     <span class="n">BigInteger</span><span class="p">(</span><span class="n">ullong</span> <span class="n">num</span><span class="p">);</span>
  339.  
  340.     <span class="c1">//Operators</span>
  341.     <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="k">operator</span><span class="o">+=</span> <span class="p">(</span><span class="k">const</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">bi</span><span class="p">);</span>
  342.     <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="k">operator</span><span class="o">-=</span> <span class="p">(</span><span class="k">const</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">bi</span><span class="p">);</span>
  343.     <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="k">operator</span><span class="o">*=</span> <span class="p">(</span><span class="k">const</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">bi</span><span class="p">);</span>
  344.     <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="k">operator</span><span class="o">/=</span> <span class="p">(</span><span class="k">const</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">bi</span><span class="p">);</span>
  345.     <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="k">operator</span><span class="o">%=</span> <span class="p">(</span><span class="k">const</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">bi</span><span class="p">);</span>
  346.     <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="k">operator</span><span class="o">/=</span> <span class="p">(</span><span class="n">ullong</span> <span class="n">n</span><span class="p">);</span>
  347.     <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="k">operator</span><span class="o">%=</span> <span class="p">(</span><span class="n">ullong</span> <span class="n">n</span><span class="p">);</span>
  348.     <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="k">operator</span><span class="o">*=</span> <span class="p">(</span><span class="n">ullong</span> <span class="n">n</span><span class="p">);</span>
  349.     <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="k">operator</span><span class="o">&lt;&lt;=</span> <span class="p">(</span><span class="n">ullong</span> <span class="n">n</span><span class="p">);</span>
  350.     <span class="c1">//TODO: operator&gt;&gt;=</span>
  351.  
  352.     <span class="n">BigInteger</span> <span class="k">operator</span><span class="o">+</span> <span class="p">(</span><span class="k">const</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">bi</span><span class="p">)</span> <span class="k">const</span><span class="p">;</span>
  353.     <span class="n">BigInteger</span> <span class="k">operator</span><span class="o">-</span> <span class="p">(</span><span class="k">const</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">bi</span><span class="p">)</span> <span class="k">const</span><span class="p">;</span>
  354.     <span class="n">BigInteger</span> <span class="k">operator</span><span class="o">*</span> <span class="p">(</span><span class="k">const</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">bi</span><span class="p">)</span> <span class="k">const</span><span class="p">;</span>
  355.     <span class="n">BigInteger</span> <span class="k">operator</span><span class="o">/</span> <span class="p">(</span><span class="k">const</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">bi</span><span class="p">)</span> <span class="k">const</span><span class="p">;</span>
  356.     <span class="n">BigInteger</span> <span class="k">operator</span><span class="o">%</span> <span class="p">(</span><span class="k">const</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">bi</span><span class="p">)</span> <span class="k">const</span><span class="p">;</span>
  357.     <span class="n">BigInteger</span> <span class="k">operator</span><span class="o">*</span> <span class="p">(</span><span class="n">ullong</span> <span class="n">n</span><span class="p">)</span> <span class="k">const</span><span class="p">;</span>
  358.     <span class="n">BigInteger</span> <span class="k">operator</span><span class="o">/</span> <span class="p">(</span><span class="n">ullong</span> <span class="n">n</span><span class="p">)</span> <span class="k">const</span><span class="p">;</span>
  359.     <span class="n">BigInteger</span> <span class="k">operator</span><span class="o">%</span> <span class="p">(</span><span class="n">ullong</span> <span class="n">n</span><span class="p">)</span> <span class="k">const</span><span class="p">;</span>
  360.     <span class="n">BigInteger</span> <span class="k">operator</span><span class="o">&lt;&lt;</span> <span class="p">(</span><span class="n">ullong</span> <span class="n">n</span><span class="p">)</span> <span class="k">const</span><span class="p">;</span>
  361.     <span class="c1">//TODO: operator&gt;&gt;</span>
  362.  
  363.     <span class="c1">//Comparison operators</span>
  364.     <span class="kt">bool</span> <span class="k">operator</span><span class="o">==</span> <span class="p">(</span><span class="k">const</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">other</span><span class="p">)</span> <span class="k">const</span><span class="p">;</span>
  365.     <span class="kt">bool</span> <span class="k">operator</span><span class="o">==</span> <span class="p">(</span><span class="n">ullong</span> <span class="n">other</span><span class="p">)</span> <span class="k">const</span><span class="p">;</span>
  366.     <span class="kt">bool</span> <span class="k">operator</span><span class="o">&lt;</span> <span class="p">(</span><span class="k">const</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">other</span><span class="p">)</span> <span class="k">const</span><span class="p">;</span>
  367.     <span class="kt">bool</span> <span class="k">operator</span><span class="o">&lt;</span> <span class="p">(</span><span class="n">ullong</span> <span class="n">other</span><span class="p">)</span> <span class="k">const</span><span class="p">;</span>
  368.     <span class="kt">bool</span> <span class="k">operator</span><span class="o">&gt;</span> <span class="p">(</span><span class="k">const</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">other</span><span class="p">)</span> <span class="k">const</span><span class="p">;</span>
  369.     <span class="kt">bool</span> <span class="k">operator</span><span class="o">&gt;</span> <span class="p">(</span><span class="n">ullong</span> <span class="n">other</span><span class="p">)</span> <span class="k">const</span><span class="p">;</span>
  370.     <span class="kt">bool</span> <span class="k">operator</span><span class="o">&lt;=</span> <span class="p">(</span><span class="k">const</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">other</span><span class="p">)</span> <span class="k">const</span><span class="p">;</span>
  371.     <span class="kt">bool</span> <span class="k">operator</span><span class="o">&lt;=</span> <span class="p">(</span><span class="n">ullong</span> <span class="n">other</span><span class="p">)</span> <span class="k">const</span><span class="p">;</span>
  372.     <span class="kt">bool</span> <span class="k">operator</span><span class="o">&gt;=</span> <span class="p">(</span><span class="k">const</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">other</span><span class="p">)</span> <span class="k">const</span><span class="p">;</span>
  373.     <span class="kt">bool</span> <span class="k">operator</span><span class="o">&gt;=</span> <span class="p">(</span><span class="n">ullong</span> <span class="n">other</span><span class="p">)</span> <span class="k">const</span><span class="p">;</span>
  374.     <span class="kt">bool</span> <span class="k">operator</span><span class="o">!=</span> <span class="p">(</span><span class="k">const</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">other</span><span class="p">)</span> <span class="k">const</span><span class="p">;</span>
  375.     <span class="kt">bool</span> <span class="k">operator</span><span class="o">!=</span> <span class="p">(</span><span class="n">ullong</span> <span class="n">other</span><span class="p">)</span> <span class="k">const</span><span class="p">;</span>
  376.  
  377.     <span class="c1">//Helper functions</span>
  378.     <span class="kt">void</span> <span class="n">normalize</span><span class="p">();</span>
  379.     <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">addZeroes</span><span class="p">(</span><span class="n">ullong</span> <span class="n">n</span><span class="p">);</span>
  380.     <span class="n">std</span><span class="o">::</span><span class="n">string</span> <span class="n">toString</span><span class="p">();</span>
  381. <span class="p">};</span>
  382.  
  383. <span class="c1">//Helper classes and functors</span>
  384. <span class="k">struct</span> <span class="n">Add</span> <span class="p">{</span>
  385.     <span class="n">ullong</span> <span class="k">operator</span><span class="p">()(</span><span class="n">ullong</span> <span class="n">a</span><span class="p">,</span> <span class="n">ullong</span> <span class="n">b</span><span class="p">)</span> <span class="p">{</span>
  386.         <span class="k">return</span> <span class="n">a</span> <span class="o">+</span> <span class="n">b</span><span class="p">;</span>
  387.     <span class="p">}</span>
  388. <span class="p">};</span>
  389.  
  390. <span class="k">struct</span> <span class="n">Multiply</span> <span class="p">{</span>
  391.     <span class="n">ullong</span> <span class="n">k</span><span class="p">;</span>
  392.  
  393.     <span class="n">Multiply</span><span class="p">()</span> <span class="p">{}</span>
  394.     <span class="n">Multiply</span><span class="p">(</span><span class="n">ullong</span> <span class="n">n</span><span class="p">)</span><span class="o">:</span> <span class="n">k</span><span class="p">(</span><span class="n">n</span><span class="p">)</span> <span class="p">{}</span>
  395.  
  396.     <span class="n">ullong</span> <span class="k">operator</span><span class="p">()(</span><span class="n">ullong</span> <span class="n">a</span><span class="p">)</span> <span class="p">{</span>
  397.         <span class="k">return</span> <span class="n">a</span> <span class="o">*</span> <span class="n">k</span><span class="p">;</span>
  398.     <span class="p">}</span>
  399. <span class="p">};</span>
  400.  
  401. <span class="k">struct</span> <span class="n">Carry</span> <span class="p">{</span>
  402.     <span class="n">ullong</span><span class="o">&amp;</span> <span class="n">carry</span><span class="p">;</span>
  403.  
  404.     <span class="n">Carry</span><span class="p">(</span><span class="n">ullong</span><span class="o">&amp;</span> <span class="n">c</span><span class="p">)</span><span class="o">:</span> <span class="n">carry</span><span class="p">(</span><span class="n">c</span><span class="p">)</span> <span class="p">{}</span>
  405.  
  406.     <span class="n">ullong</span> <span class="k">operator</span><span class="p">()(</span><span class="n">ullong</span> <span class="n">n</span><span class="p">)</span>
  407.     <span class="p">{</span>
  408.         <span class="n">n</span> <span class="o">+=</span> <span class="n">carry</span><span class="p">;</span>
  409.         <span class="n">carry</span> <span class="o">=</span> <span class="n">n</span> <span class="o">/</span> <span class="n">BigInteger</span><span class="o">::</span><span class="n">base</span><span class="p">;</span>
  410.         <span class="n">n</span> <span class="o">%=</span> <span class="n">BigInteger</span><span class="o">::</span><span class="n">base</span><span class="p">;</span>
  411.  
  412.         <span class="k">return</span> <span class="n">n</span><span class="p">;</span>
  413.     <span class="p">}</span>
  414. <span class="p">};</span>
  415.  
  416. <span class="k">template</span> <span class="o">&lt;</span><span class="k">class</span> <span class="nc">BaseOperator</span><span class="o">&gt;</span>
  417. <span class="k">struct</span> <span class="nl">OperatorCarry:</span> <span class="k">public</span> <span class="n">BaseOperator</span><span class="p">,</span> <span class="k">public</span> <span class="n">Carry</span> <span class="p">{</span>
  418.     <span class="n">OperatorCarry</span><span class="p">(</span><span class="n">ullong</span><span class="o">&amp;</span> <span class="n">c</span><span class="p">)</span><span class="o">:</span> <span class="n">Carry</span><span class="p">(</span><span class="n">c</span><span class="p">)</span> <span class="p">{}</span>
  419.  
  420.     <span class="n">ullong</span> <span class="k">operator</span><span class="p">()(</span><span class="n">ullong</span> <span class="n">a</span><span class="p">)</span> <span class="p">{</span>
  421.         <span class="k">return</span> <span class="n">Carry</span><span class="o">::</span><span class="k">operator</span><span class="p">()(</span><span class="n">BaseOperator</span><span class="o">::</span><span class="k">operator</span><span class="p">()(</span><span class="n">a</span><span class="p">));</span>
  422.     <span class="p">}</span>
  423.     <span class="n">ullong</span> <span class="k">operator</span><span class="p">()(</span><span class="n">ullong</span> <span class="n">a</span><span class="p">,</span> <span class="n">ullong</span> <span class="n">b</span><span class="p">)</span> <span class="p">{</span>
  424.         <span class="k">return</span> <span class="n">Carry</span><span class="o">::</span><span class="k">operator</span><span class="p">()(</span><span class="n">BaseOperator</span><span class="o">::</span><span class="k">operator</span><span class="p">()(</span><span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">));</span>
  425.     <span class="p">}</span>
  426. <span class="p">};</span>
  427.  
  428. <span class="k">struct</span> <span class="n">Borrow</span> <span class="p">{</span>
  429.     <span class="kt">long</span> <span class="kt">long</span><span class="o">&amp;</span> <span class="n">borrow</span><span class="p">;</span>
  430.  
  431.     <span class="n">Borrow</span><span class="p">(</span><span class="kt">long</span> <span class="kt">long</span><span class="o">&amp;</span> <span class="n">b</span><span class="p">)</span><span class="o">:</span> <span class="n">borrow</span><span class="p">(</span><span class="n">b</span><span class="p">)</span> <span class="p">{}</span>
  432.  
  433.     <span class="n">ullong</span> <span class="k">operator</span><span class="p">()(</span><span class="kt">long</span> <span class="kt">long</span> <span class="n">n</span><span class="p">)</span> <span class="p">{</span>
  434.         <span class="n">n</span> <span class="o">-=</span> <span class="n">borrow</span><span class="p">;</span>
  435.         <span class="n">borrow</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
  436.         <span class="k">while</span> <span class="p">(</span><span class="n">n</span> <span class="o">&lt;</span> <span class="mi">0</span><span class="p">)</span> <span class="p">{</span>
  437.             <span class="n">n</span> <span class="o">+=</span> <span class="n">BigInteger</span><span class="o">::</span><span class="n">base</span><span class="p">;</span>
  438.             <span class="o">++</span><span class="n">borrow</span><span class="p">;</span>
  439.         <span class="p">}</span>
  440.         <span class="k">return</span> <span class="n">n</span><span class="p">;</span>
  441.     <span class="p">}</span>
  442. <span class="p">};</span>
  443.  
  444. <span class="k">struct</span> <span class="n">SubtractionBorrow</span> <span class="p">{</span>
  445.     <span class="kt">long</span> <span class="kt">long</span><span class="o">&amp;</span> <span class="n">borrow</span><span class="p">;</span>
  446.  
  447.     <span class="n">SubtractionBorrow</span><span class="p">(</span><span class="kt">long</span> <span class="kt">long</span><span class="o">&amp;</span> <span class="n">b</span><span class="p">)</span><span class="o">:</span> <span class="n">borrow</span><span class="p">(</span><span class="n">b</span><span class="p">)</span> <span class="p">{}</span>
  448.  
  449.     <span class="n">ullong</span> <span class="k">operator</span><span class="p">()(</span><span class="kt">long</span> <span class="kt">long</span> <span class="n">a</span><span class="p">,</span> <span class="kt">long</span> <span class="kt">long</span> <span class="n">b</span><span class="p">)</span> <span class="p">{</span>
  450.         <span class="kt">long</span> <span class="kt">long</span> <span class="n">n</span> <span class="o">=</span> <span class="n">b</span> <span class="o">-</span> <span class="n">a</span> <span class="o">-</span> <span class="n">borrow</span><span class="p">;</span>
  451.         <span class="n">borrow</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
  452.         <span class="k">while</span> <span class="p">(</span><span class="n">n</span> <span class="o">&lt;</span> <span class="mi">0</span><span class="p">)</span> <span class="p">{</span>
  453.             <span class="n">n</span> <span class="o">+=</span> <span class="n">BigInteger</span><span class="o">::</span><span class="n">base</span><span class="p">;</span>
  454.             <span class="o">++</span><span class="n">borrow</span><span class="p">;</span>
  455.         <span class="p">}</span>
  456.         <span class="k">return</span> <span class="n">n</span><span class="p">;</span>
  457.     <span class="p">}</span>
  458. <span class="p">};</span>
  459.  
  460. <span class="n">BigInteger</span><span class="o">::</span><span class="n">BigInteger</span><span class="p">()</span> <span class="p">{</span>
  461.     <span class="n">digits</span><span class="p">.</span><span class="n">assign</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="mi">0</span><span class="p">);</span>
  462. <span class="p">}</span>
  463.  
  464. <span class="n">BigInteger</span><span class="o">::</span><span class="n">BigInteger</span><span class="p">(</span><span class="n">ullong</span> <span class="n">num</span><span class="p">)</span> <span class="p">{</span>
  465.     <span class="n">std</span><span class="o">::</span><span class="n">stringstream</span> <span class="n">buffer</span><span class="p">;</span>
  466.     <span class="n">buffer</span> <span class="o">&lt;&lt;</span> <span class="n">num</span><span class="p">;</span>
  467.     <span class="o">*</span><span class="k">this</span> <span class="o">=</span> <span class="n">BigInteger</span><span class="p">(</span><span class="n">buffer</span><span class="p">.</span><span class="n">str</span><span class="p">());</span>
  468. <span class="p">}</span>
  469.  
  470. <span class="n">BigInteger</span><span class="o">::</span><span class="n">BigInteger</span><span class="p">(</span><span class="n">std</span><span class="o">::</span><span class="n">string</span> <span class="n">str</span><span class="p">)</span> <span class="p">{</span>
  471.     <span class="n">std</span><span class="o">::</span><span class="n">reverse</span><span class="p">(</span><span class="n">str</span><span class="p">.</span><span class="n">begin</span><span class="p">(),</span> <span class="n">str</span><span class="p">.</span><span class="n">end</span><span class="p">());</span>
  472.  
  473.     <span class="k">while</span> <span class="p">(</span><span class="n">str</span><span class="p">.</span><span class="n">size</span><span class="p">()</span> <span class="o">%</span> <span class="n">BigInteger</span><span class="o">::</span><span class="n">N</span> <span class="o">!=</span> <span class="mi">0</span><span class="p">)</span>
  474.         <span class="n">str</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="sc">'0'</span><span class="p">);</span>
  475.  
  476.     <span class="n">std</span><span class="o">::</span><span class="n">reverse</span><span class="p">(</span><span class="n">str</span><span class="p">.</span><span class="n">begin</span><span class="p">(),</span> <span class="n">str</span><span class="p">.</span><span class="n">end</span><span class="p">());</span>
  477.  
  478.     <span class="n">ullong</span> <span class="n">position</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
  479.     <span class="n">ullong</span> <span class="n">size</span> <span class="o">=</span> <span class="n">str</span><span class="p">.</span><span class="n">size</span><span class="p">();</span>
  480.  
  481.     <span class="k">while</span><span class="p">(</span><span class="n">position</span> <span class="o">!=</span> <span class="n">size</span><span class="p">)</span> <span class="p">{</span>
  482.         <span class="n">std</span><span class="o">::</span><span class="n">stringstream</span> <span class="n">buffer</span><span class="p">(</span><span class="n">str</span><span class="p">.</span><span class="n">substr</span><span class="p">(</span><span class="n">position</span><span class="p">,</span> <span class="n">BigInteger</span><span class="o">::</span><span class="n">N</span><span class="p">));</span>
  483.         <span class="n">ullong</span> <span class="n">digit</span><span class="p">;</span>
  484.         <span class="n">buffer</span> <span class="o">&gt;&gt;</span> <span class="n">digit</span><span class="p">;</span>
  485.         <span class="n">digits</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="n">digit</span><span class="p">);</span>
  486.  
  487.         <span class="n">position</span> <span class="o">+=</span> <span class="n">BigInteger</span><span class="o">::</span><span class="n">N</span><span class="p">;</span>
  488.     <span class="p">}</span>
  489.  
  490.     <span class="n">std</span><span class="o">::</span><span class="n">reverse</span><span class="p">(</span><span class="n">digits</span><span class="p">.</span><span class="n">begin</span><span class="p">(),</span> <span class="n">digits</span><span class="p">.</span><span class="n">end</span><span class="p">());</span>
  491. <span class="p">}</span>
  492.  
  493. <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">BigInteger</span><span class="o">::</span><span class="k">operator</span><span class="o">+=</span> <span class="p">(</span><span class="k">const</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">bi</span><span class="p">)</span> <span class="p">{</span>
  494.     <span class="k">if</span> <span class="p">(</span><span class="n">digits</span><span class="p">.</span><span class="n">size</span><span class="p">()</span> <span class="o">&lt;</span> <span class="n">bi</span><span class="p">.</span><span class="n">digits</span><span class="p">.</span><span class="n">size</span><span class="p">())</span>
  495.         <span class="n">digits</span><span class="p">.</span><span class="n">resize</span><span class="p">(</span><span class="n">bi</span><span class="p">.</span><span class="n">digits</span><span class="p">.</span><span class="n">size</span><span class="p">());</span>
  496.  
  497.     <span class="n">ullong</span> <span class="n">carry</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
  498.     <span class="n">std</span><span class="o">::</span><span class="n">deque</span><span class="o">&lt;</span><span class="n">ullong</span><span class="o">&gt;::</span><span class="n">iterator</span> <span class="n">it</span><span class="p">;</span>
  499.  
  500.     <span class="n">OperatorCarry</span><span class="o">&lt;</span><span class="n">Add</span><span class="o">&gt;</span> <span class="n">addwc</span><span class="p">(</span><span class="n">carry</span><span class="p">);</span>
  501.  
  502.     <span class="n">it</span> <span class="o">=</span> <span class="n">std</span><span class="o">::</span><span class="n">transform</span><span class="p">(</span><span class="n">bi</span><span class="p">.</span><span class="n">digits</span><span class="p">.</span><span class="n">begin</span><span class="p">(),</span> <span class="n">bi</span><span class="p">.</span><span class="n">digits</span><span class="p">.</span><span class="n">end</span><span class="p">(),</span> <span class="n">digits</span><span class="p">.</span><span class="n">begin</span><span class="p">(),</span> <span class="n">digits</span><span class="p">.</span><span class="n">begin</span><span class="p">(),</span> <span class="n">addwc</span><span class="p">);</span>
  503.  
  504.     <span class="n">std</span><span class="o">::</span><span class="n">transform</span><span class="p">(</span><span class="n">it</span><span class="p">,</span> <span class="n">digits</span><span class="p">.</span><span class="n">end</span><span class="p">(),</span> <span class="n">it</span><span class="p">,</span> <span class="n">Carry</span><span class="p">(</span><span class="n">carry</span><span class="p">));</span>
  505.  
  506.     <span class="k">if</span><span class="p">(</span><span class="n">carry</span><span class="p">)</span>
  507.         <span class="n">digits</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="n">carry</span><span class="p">);</span>
  508.  
  509.     <span class="k">return</span> <span class="o">*</span><span class="k">this</span><span class="p">;</span>
  510. <span class="p">}</span>
  511.  
  512. <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">BigInteger</span><span class="o">::</span><span class="k">operator</span><span class="o">-=</span> <span class="p">(</span><span class="k">const</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">bi</span><span class="p">)</span> <span class="p">{</span>
  513.     <span class="kt">long</span> <span class="kt">long</span> <span class="n">borrow</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
  514.     <span class="n">std</span><span class="o">::</span><span class="n">deque</span><span class="o">&lt;</span><span class="n">ullong</span><span class="o">&gt;::</span><span class="n">iterator</span> <span class="n">it</span><span class="p">;</span>
  515.  
  516.     <span class="n">it</span> <span class="o">=</span> <span class="n">std</span><span class="o">::</span><span class="n">transform</span><span class="p">(</span><span class="n">bi</span><span class="p">.</span><span class="n">digits</span><span class="p">.</span><span class="n">begin</span><span class="p">(),</span> <span class="n">bi</span><span class="p">.</span><span class="n">digits</span><span class="p">.</span><span class="n">end</span><span class="p">(),</span> <span class="n">digits</span><span class="p">.</span><span class="n">begin</span><span class="p">(),</span> <span class="n">digits</span><span class="p">.</span><span class="n">begin</span><span class="p">(),</span> <span class="n">SubtractionBorrow</span><span class="p">(</span><span class="n">borrow</span><span class="p">));</span>
  517.  
  518.     <span class="n">std</span><span class="o">::</span><span class="n">transform</span><span class="p">(</span><span class="n">it</span><span class="p">,</span> <span class="n">digits</span><span class="p">.</span><span class="n">end</span><span class="p">(),</span> <span class="n">it</span><span class="p">,</span> <span class="n">Borrow</span><span class="p">(</span><span class="n">borrow</span><span class="p">));</span>
  519.  
  520.     <span class="k">return</span> <span class="o">*</span><span class="k">this</span><span class="p">;</span>
  521. <span class="p">}</span>
  522.  
  523. <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">BigInteger</span><span class="o">::</span><span class="k">operator</span><span class="o">*=</span> <span class="p">(</span><span class="n">ullong</span> <span class="n">n</span><span class="p">)</span> <span class="p">{</span>
  524.     <span class="n">ullong</span> <span class="n">carry</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
  525.  
  526.     <span class="n">OperatorCarry</span><span class="o">&lt;</span><span class="n">Multiply</span><span class="o">&gt;</span> <span class="n">mulmc</span><span class="p">(</span><span class="n">carry</span><span class="p">);</span>
  527.     <span class="n">mulmc</span><span class="p">.</span><span class="n">k</span> <span class="o">=</span> <span class="n">n</span><span class="p">;</span>
  528.  
  529.     <span class="n">std</span><span class="o">::</span><span class="n">transform</span><span class="p">(</span><span class="n">digits</span><span class="p">.</span><span class="n">begin</span><span class="p">(),</span> <span class="n">digits</span><span class="p">.</span><span class="n">end</span><span class="p">(),</span> <span class="n">digits</span><span class="p">.</span><span class="n">begin</span><span class="p">(),</span> <span class="n">mulmc</span><span class="p">);</span>
  530.  
  531.     <span class="k">while</span><span class="p">(</span><span class="n">carry</span><span class="p">)</span> <span class="p">{</span>
  532.         <span class="n">digits</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="n">carry</span> <span class="o">%</span> <span class="n">BigInteger</span><span class="o">::</span><span class="n">base</span><span class="p">);</span>
  533.         <span class="n">carry</span> <span class="o">/=</span> <span class="n">BigInteger</span><span class="o">::</span><span class="n">base</span><span class="p">;</span>
  534.     <span class="p">}</span>
  535.  
  536.     <span class="k">return</span> <span class="o">*</span><span class="k">this</span><span class="p">;</span>
  537. <span class="p">}</span>
  538.  
  539. <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">BigInteger</span><span class="o">::</span><span class="k">operator</span><span class="o">*=</span> <span class="p">(</span><span class="k">const</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">bi</span><span class="p">)</span> <span class="p">{</span>
  540.     <span class="k">const</span> <span class="n">BigInteger</span><span class="o">*</span> <span class="n">maxOp</span> <span class="o">=</span> <span class="k">this</span><span class="p">;</span>
  541.     <span class="k">const</span> <span class="n">BigInteger</span><span class="o">*</span> <span class="n">minOp</span> <span class="o">=</span> <span class="o">&amp;</span><span class="n">bi</span><span class="p">;</span>
  542.  
  543.     <span class="n">ullong</span> <span class="n">maxSize</span> <span class="o">=</span> <span class="n">maxOp</span><span class="o">-&gt;</span><span class="n">digits</span><span class="p">.</span><span class="n">size</span><span class="p">();</span>
  544.     <span class="n">ullong</span> <span class="n">minSize</span> <span class="o">=</span> <span class="n">minOp</span><span class="o">-&gt;</span><span class="n">digits</span><span class="p">.</span><span class="n">size</span><span class="p">();</span>
  545.  
  546.     <span class="k">if</span> <span class="p">(</span><span class="n">maxSize</span> <span class="o">&lt;</span> <span class="n">minSize</span><span class="p">)</span> <span class="p">{</span>
  547.         <span class="n">std</span><span class="o">::</span><span class="n">swap</span><span class="p">(</span><span class="n">maxOp</span><span class="p">,</span> <span class="n">minOp</span><span class="p">);</span>
  548.         <span class="n">std</span><span class="o">::</span><span class="n">swap</span><span class="p">(</span><span class="n">maxSize</span><span class="p">,</span> <span class="n">minSize</span><span class="p">);</span>
  549.     <span class="p">}</span>
  550.  
  551.     <span class="n">std</span><span class="o">::</span><span class="n">deque</span><span class="o">&lt;</span><span class="n">BigInteger</span><span class="o">&gt;</span> <span class="n">array</span><span class="p">(</span><span class="n">minSize</span><span class="p">);</span>
  552.  
  553.     <span class="k">for</span> <span class="p">(</span><span class="n">ullong</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">minSize</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span><span class="p">)</span> <span class="p">{</span>
  554.         <span class="n">array</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">digits</span><span class="p">.</span><span class="n">resize</span><span class="p">(</span><span class="n">maxSize</span><span class="p">);</span>
  555.         <span class="n">array</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="o">*</span><span class="n">maxOp</span> <span class="o">*</span> <span class="n">minOp</span><span class="o">-&gt;</span><span class="n">digits</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
  556.     <span class="p">}</span>
  557.  
  558.     <span class="o">*</span><span class="k">this</span> <span class="o">=</span> <span class="n">array</span><span class="p">[</span><span class="mi">0</span><span class="p">];</span>
  559.     <span class="n">digits</span><span class="p">.</span><span class="n">resize</span><span class="p">(</span><span class="n">maxSize</span> <span class="o">+</span> <span class="n">minSize</span><span class="p">);</span>
  560.  
  561.     <span class="k">for</span> <span class="p">(</span><span class="n">ullong</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">minSize</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span><span class="p">)</span> <span class="p">{</span>
  562.         <span class="n">array</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">addZeroes</span><span class="p">(</span><span class="n">i</span><span class="p">);</span>
  563.         <span class="o">*</span><span class="k">this</span> <span class="o">+=</span> <span class="n">array</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
  564.     <span class="p">}</span>
  565.  
  566.     <span class="k">return</span> <span class="o">*</span><span class="k">this</span><span class="p">;</span>
  567. <span class="p">}</span>
  568.  
  569. <span class="kt">void</span> <span class="n">divideHelper</span><span class="p">(</span><span class="k">const</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">top</span><span class="p">,</span> <span class="k">const</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">bot</span><span class="p">,</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">q</span><span class="p">,</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">r</span><span class="p">)</span> <span class="p">{</span>
  570.     <span class="k">if</span><span class="p">(</span><span class="n">top</span> <span class="o">&lt;</span> <span class="n">bot</span><span class="p">)</span> <span class="p">{</span>
  571.         <span class="n">q</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
  572.         <span class="n">r</span> <span class="o">=</span> <span class="n">top</span><span class="p">;</span>
  573.         <span class="k">return</span><span class="p">;</span>
  574.     <span class="p">}</span>
  575.     <span class="k">else</span> <span class="k">if</span><span class="p">(</span><span class="n">top</span> <span class="o">==</span> <span class="n">bot</span><span class="p">)</span> <span class="p">{</span>
  576.         <span class="n">q</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
  577.         <span class="n">r</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
  578.         <span class="k">return</span><span class="p">;</span>
  579.     <span class="p">}</span>
  580.     <span class="n">BigInteger</span> <span class="n">dividend</span><span class="p">(</span><span class="n">top</span><span class="p">);</span>
  581.     <span class="n">BigInteger</span> <span class="n">divisor</span><span class="p">(</span><span class="n">bot</span><span class="p">);</span>
  582.     <span class="n">q</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
  583.     <span class="n">r</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
  584.     <span class="n">ullong</span> <span class="n">tr</span><span class="p">;</span>
  585.     <span class="n">ullong</span> <span class="n">zero</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
  586.  
  587.     <span class="k">while</span><span class="p">(</span><span class="n">divisor</span><span class="p">.</span><span class="n">digits</span><span class="p">.</span><span class="n">size</span><span class="p">()</span> <span class="o">&lt;</span> <span class="n">dividend</span><span class="p">.</span><span class="n">digits</span><span class="p">.</span><span class="n">size</span><span class="p">())</span> <span class="p">{</span>
  588.         <span class="n">divisor</span> <span class="o">*=</span> <span class="n">BigInteger</span><span class="o">::</span><span class="n">base</span><span class="p">;</span>
  589.         <span class="n">zero</span><span class="o">++</span><span class="p">;</span>
  590.     <span class="p">}</span>
  591.     <span class="k">if</span><span class="p">(</span><span class="n">divisor</span> <span class="o">&gt;</span> <span class="n">dividend</span><span class="p">)</span> <span class="p">{</span>
  592.         <span class="n">divisor</span> <span class="o">/=</span> <span class="n">BigInteger</span><span class="o">::</span><span class="n">base</span><span class="p">;</span>
  593.         <span class="n">zero</span><span class="o">--</span><span class="p">;</span>
  594.     <span class="p">}</span>
  595.     <span class="kt">int</span> <span class="n">divisor1</span> <span class="o">=</span> <span class="n">divisor</span><span class="p">.</span><span class="n">digits</span><span class="p">[</span><span class="n">divisor</span><span class="p">.</span><span class="n">digits</span><span class="p">.</span><span class="n">size</span><span class="p">()</span><span class="o">-</span><span class="mi">1</span><span class="p">];</span>
  596.     <span class="kt">int</span> <span class="n">dividend1</span><span class="p">;</span>
  597.     <span class="n">BigInteger</span> <span class="n">holder</span><span class="p">;</span>
  598.     <span class="k">for</span><span class="p">(</span><span class="n">ullong</span> <span class="n">k</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">k</span> <span class="o">&lt;=</span> <span class="n">zero</span><span class="p">;</span> <span class="o">++</span><span class="n">k</span><span class="p">)</span> <span class="p">{</span>
  599.         <span class="n">dividend1</span> <span class="o">=</span> <span class="n">dividend</span><span class="p">.</span><span class="n">digits</span><span class="p">[</span><span class="n">dividend</span><span class="p">.</span><span class="n">digits</span><span class="p">.</span><span class="n">size</span><span class="p">()</span><span class="o">-</span><span class="mi">1</span><span class="p">];</span>
  600.         <span class="n">tr</span> <span class="o">=</span> <span class="p">(</span><span class="n">dividend1</span><span class="o">*</span><span class="n">BigInteger</span><span class="o">::</span><span class="n">base</span> <span class="o">+</span> <span class="n">dividend</span><span class="p">.</span><span class="n">digits</span><span class="p">[</span><span class="n">dividend</span><span class="p">.</span><span class="n">digits</span><span class="p">.</span><span class="n">size</span><span class="p">()</span><span class="o">-</span><span class="mi">2</span><span class="p">])</span><span class="o">/</span><span class="n">divisor1</span><span class="p">;</span>
  601.         <span class="k">if</span><span class="p">(</span><span class="n">BigInteger</span><span class="o">::</span><span class="n">base</span> <span class="o">&lt;=</span> <span class="n">tr</span><span class="p">)</span> <span class="p">{</span>
  602.             <span class="n">tr</span> <span class="o">=</span> <span class="n">BigInteger</span><span class="o">::</span><span class="n">base</span> <span class="o">-</span><span class="mi">1</span><span class="p">;</span>
  603.         <span class="p">}</span>
  604.         <span class="k">while</span><span class="p">((</span><span class="n">holder</span> <span class="o">=</span> <span class="n">divisor</span><span class="o">*</span><span class="n">tr</span><span class="p">)</span> <span class="o">&gt;</span> <span class="n">dividend</span><span class="p">)</span> <span class="p">{</span>
  605.             <span class="n">tr</span><span class="o">--</span><span class="p">;</span>
  606.         <span class="p">}</span>
  607.         <span class="n">q</span> <span class="o">*=</span> <span class="n">BigInteger</span><span class="o">::</span><span class="n">base</span><span class="p">;</span>
  608.         <span class="n">q</span> <span class="o">+=</span> <span class="n">tr</span><span class="p">;</span>
  609.         <span class="n">dividend</span> <span class="o">-=</span> <span class="n">holder</span><span class="p">;</span>
  610.         <span class="n">divisor</span> <span class="o">/=</span> <span class="n">BigInteger</span><span class="o">::</span><span class="n">base</span><span class="p">;</span>
  611.         <span class="n">divisor1</span> <span class="o">=</span> <span class="n">divisor</span><span class="p">.</span><span class="n">digits</span><span class="p">[</span><span class="n">divisor</span><span class="p">.</span><span class="n">digits</span><span class="p">.</span><span class="n">size</span><span class="p">()</span><span class="o">-</span><span class="mi">1</span><span class="p">];</span>
  612.     <span class="p">}</span>
  613.     <span class="n">r</span> <span class="o">=</span> <span class="n">dividend</span><span class="p">;</span>
  614. <span class="p">}</span>
  615.  
  616. <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">BigInteger</span><span class="o">::</span><span class="k">operator</span><span class="o">/=</span> <span class="p">(</span><span class="k">const</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">bi</span><span class="p">)</span> <span class="p">{</span>
  617.     <span class="n">BigInteger</span> <span class="n">q</span><span class="p">,</span> <span class="n">r</span><span class="p">;</span>
  618.     <span class="n">divideHelper</span><span class="p">(</span><span class="o">*</span><span class="k">this</span><span class="p">,</span><span class="n">bi</span><span class="p">,</span><span class="n">q</span><span class="p">,</span><span class="n">r</span><span class="p">);</span>
  619.     <span class="o">*</span><span class="k">this</span> <span class="o">=</span> <span class="n">q</span><span class="p">;</span>
  620.     <span class="n">normalize</span><span class="p">();</span>
  621.     <span class="k">return</span> <span class="o">*</span><span class="k">this</span><span class="p">;</span>
  622. <span class="p">}</span>
  623.  
  624. <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">BigInteger</span><span class="o">::</span><span class="k">operator</span><span class="o">%=</span> <span class="p">(</span><span class="k">const</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">bi</span><span class="p">)</span> <span class="p">{</span>
  625.     <span class="n">BigInteger</span> <span class="n">q</span><span class="p">,</span> <span class="n">r</span><span class="p">;</span>
  626.     <span class="n">divideHelper</span><span class="p">(</span><span class="o">*</span><span class="k">this</span><span class="p">,</span><span class="n">bi</span><span class="p">,</span><span class="n">q</span><span class="p">,</span><span class="n">r</span><span class="p">);</span>
  627.     <span class="o">*</span><span class="k">this</span> <span class="o">=</span> <span class="n">r</span><span class="p">;</span>
  628.     <span class="k">return</span> <span class="o">*</span><span class="k">this</span><span class="p">;</span>
  629. <span class="p">}</span>
  630.  
  631. <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">BigInteger</span><span class="o">::</span><span class="k">operator</span><span class="o">/=</span> <span class="p">(</span><span class="n">ullong</span> <span class="n">n</span><span class="p">)</span> <span class="p">{</span>
  632.     <span class="n">ullong</span> <span class="n">carry</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
  633.     <span class="n">ullong</span> <span class="n">quotient</span><span class="p">;</span>
  634.  
  635.     <span class="n">ullong</span> <span class="n">length</span> <span class="o">=</span> <span class="n">digits</span><span class="p">.</span><span class="n">size</span><span class="p">();</span>
  636.  
  637.     <span class="k">if</span><span class="p">(</span><span class="n">n</span> <span class="o">&gt;</span> <span class="n">BigInteger</span><span class="o">::</span><span class="n">base</span><span class="p">)</span> <span class="p">{</span>
  638.         <span class="k">return</span> <span class="p">(</span><span class="o">*</span><span class="k">this</span> <span class="o">/=</span> <span class="n">BigInteger</span><span class="p">(</span><span class="n">n</span><span class="p">));</span>
  639.     <span class="p">}</span>
  640.     <span class="k">if</span><span class="p">(</span><span class="n">n</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span> <span class="p">{</span>
  641.         <span class="k">throw</span> <span class="n">std</span><span class="o">::</span><span class="n">logic_error</span><span class="p">(</span><span class="s">"Division by zero"</span><span class="p">);</span>
  642.     <span class="p">}</span>
  643.     <span class="k">else</span> <span class="p">{</span>
  644.         <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">k</span> <span class="o">=</span> <span class="n">length</span><span class="o">-</span><span class="mi">1</span><span class="p">;</span> <span class="n">k</span><span class="o">&gt;=</span><span class="mi">0</span><span class="p">;</span> <span class="o">--</span><span class="n">k</span><span class="p">)</span> <span class="p">{</span>
  645.             <span class="n">quotient</span> <span class="o">=</span> <span class="p">(</span><span class="n">BigInteger</span><span class="o">::</span><span class="n">base</span><span class="o">*</span><span class="n">carry</span> <span class="o">+</span> <span class="n">digits</span><span class="p">[</span><span class="n">k</span><span class="p">]);</span>
  646.             <span class="n">carry</span> <span class="o">=</span> <span class="n">quotient</span> <span class="o">%</span> <span class="n">n</span><span class="p">;</span>
  647.             <span class="n">digits</span><span class="p">[</span><span class="n">k</span><span class="p">]</span> <span class="o">=</span> <span class="n">quotient</span> <span class="o">/</span> <span class="n">n</span><span class="p">;</span>
  648.         <span class="p">}</span>
  649.     <span class="p">}</span>
  650.     <span class="n">normalize</span><span class="p">();</span>
  651.     <span class="k">return</span> <span class="o">*</span><span class="k">this</span><span class="p">;</span>
  652. <span class="p">}</span>
  653.  
  654. <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">BigInteger</span><span class="o">::</span><span class="k">operator</span><span class="o">%=</span> <span class="p">(</span><span class="n">ullong</span> <span class="n">n</span><span class="p">)</span> <span class="p">{</span>
  655.     <span class="n">BigInteger</span> <span class="n">q</span><span class="p">,</span> <span class="n">r</span><span class="p">;</span>
  656.     <span class="n">BigInteger</span> <span class="n">l</span><span class="p">(</span><span class="n">n</span><span class="p">);</span>
  657.     <span class="n">divideHelper</span><span class="p">(</span><span class="o">*</span><span class="k">this</span><span class="p">,</span><span class="n">l</span><span class="p">,</span><span class="n">q</span><span class="p">,</span><span class="n">r</span><span class="p">);</span>
  658.     <span class="o">*</span><span class="k">this</span> <span class="o">=</span> <span class="n">r</span><span class="p">;</span>
  659.     <span class="k">return</span> <span class="o">*</span><span class="k">this</span><span class="p">;</span>
  660. <span class="p">}</span>
  661.  
  662. <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">BigInteger</span><span class="o">::</span><span class="k">operator</span><span class="o">&lt;&lt;=</span> <span class="p">(</span><span class="n">ullong</span> <span class="n">n</span><span class="p">)</span> <span class="p">{</span>
  663.     <span class="k">for</span><span class="p">(</span><span class="n">ullong</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span><span class="p">)</span> <span class="p">{</span>
  664.         <span class="p">(</span><span class="o">*</span><span class="k">this</span><span class="p">)</span> <span class="o">*=</span> <span class="mi">2</span><span class="p">;</span>
  665.     <span class="p">}</span>
  666.     <span class="k">return</span> <span class="o">*</span><span class="k">this</span><span class="p">;</span>
  667. <span class="p">}</span>
  668. <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">BigInteger</span><span class="o">::</span><span class="n">addZeroes</span><span class="p">(</span><span class="n">ullong</span> <span class="n">n</span><span class="p">)</span> <span class="p">{</span>
  669.     <span class="n">digits</span><span class="p">.</span><span class="n">resize</span><span class="p">(</span><span class="n">digits</span><span class="p">.</span><span class="n">size</span><span class="p">()</span> <span class="o">+</span> <span class="n">n</span><span class="p">);</span>
  670.     <span class="n">std</span><span class="o">::</span><span class="n">copy</span><span class="p">(</span><span class="n">digits</span><span class="p">.</span><span class="n">rbegin</span><span class="p">()</span> <span class="o">+</span> <span class="n">n</span><span class="p">,</span> <span class="n">digits</span><span class="p">.</span><span class="n">rend</span><span class="p">(),</span> <span class="n">digits</span><span class="p">.</span><span class="n">rbegin</span><span class="p">());</span>
  671.     <span class="n">std</span><span class="o">::</span><span class="n">fill</span><span class="p">(</span><span class="n">digits</span><span class="p">.</span><span class="n">begin</span><span class="p">(),</span> <span class="n">digits</span><span class="p">.</span><span class="n">begin</span><span class="p">()</span> <span class="o">+</span> <span class="n">n</span><span class="p">,</span> <span class="mi">0</span><span class="p">);</span>
  672.  
  673.     <span class="k">return</span> <span class="o">*</span><span class="k">this</span><span class="p">;</span>
  674. <span class="p">}</span>
  675.  
  676. <span class="n">BigInteger</span> <span class="n">BigInteger</span><span class="o">::</span><span class="k">operator</span><span class="o">+</span> <span class="p">(</span><span class="k">const</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">bi</span><span class="p">)</span> <span class="k">const</span> <span class="p">{</span>
  677.     <span class="n">BigInteger</span> <span class="n">result</span><span class="p">(</span><span class="o">*</span><span class="k">this</span><span class="p">);</span>
  678.     <span class="k">return</span> <span class="p">(</span><span class="n">result</span>  <span class="o">+=</span> <span class="n">bi</span><span class="p">);</span>
  679. <span class="p">}</span>
  680.  
  681. <span class="n">BigInteger</span> <span class="n">BigInteger</span><span class="o">::</span><span class="k">operator</span><span class="o">-</span> <span class="p">(</span><span class="k">const</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">bi</span><span class="p">)</span> <span class="k">const</span> <span class="p">{</span>
  682.     <span class="n">BigInteger</span> <span class="n">result</span><span class="p">(</span><span class="o">*</span><span class="k">this</span><span class="p">);</span>
  683.     <span class="k">return</span> <span class="p">(</span><span class="n">result</span>  <span class="o">-=</span> <span class="n">bi</span><span class="p">);</span>
  684. <span class="p">}</span>
  685.  
  686. <span class="n">BigInteger</span> <span class="n">BigInteger</span><span class="o">::</span><span class="k">operator</span><span class="o">*</span> <span class="p">(</span><span class="n">ullong</span> <span class="n">n</span><span class="p">)</span> <span class="k">const</span> <span class="p">{</span>
  687.     <span class="n">BigInteger</span> <span class="n">result</span><span class="p">(</span><span class="o">*</span><span class="k">this</span><span class="p">);</span>
  688.     <span class="k">return</span> <span class="p">(</span><span class="n">result</span>  <span class="o">*=</span>  <span class="n">n</span><span class="p">);</span>
  689. <span class="p">}</span>
  690.  
  691. <span class="n">BigInteger</span> <span class="n">BigInteger</span><span class="o">::</span><span class="k">operator</span><span class="o">/</span> <span class="p">(</span><span class="k">const</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">bi</span><span class="p">)</span> <span class="k">const</span> <span class="p">{</span>
  692.     <span class="n">BigInteger</span> <span class="n">result</span><span class="p">(</span><span class="o">*</span><span class="k">this</span><span class="p">);</span>
  693.     <span class="k">return</span> <span class="p">(</span><span class="n">result</span> <span class="o">/=</span> <span class="n">bi</span><span class="p">);</span>
  694. <span class="p">}</span>
  695.  
  696. <span class="n">BigInteger</span> <span class="n">BigInteger</span><span class="o">::</span><span class="k">operator</span><span class="o">%</span> <span class="p">(</span><span class="k">const</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">bi</span><span class="p">)</span> <span class="k">const</span> <span class="p">{</span>
  697.     <span class="n">BigInteger</span> <span class="n">result</span><span class="p">(</span><span class="o">*</span><span class="k">this</span><span class="p">);</span>
  698.     <span class="k">return</span> <span class="p">(</span><span class="n">result</span> <span class="o">%=</span> <span class="n">bi</span><span class="p">);</span>
  699. <span class="p">}</span>
  700.  
  701. <span class="n">BigInteger</span> <span class="n">BigInteger</span><span class="o">::</span><span class="k">operator</span><span class="o">/</span> <span class="p">(</span><span class="n">ullong</span> <span class="n">n</span><span class="p">)</span> <span class="k">const</span> <span class="p">{</span>
  702.     <span class="n">BigInteger</span> <span class="n">result</span><span class="p">(</span><span class="o">*</span><span class="k">this</span><span class="p">);</span>
  703.     <span class="k">return</span> <span class="p">(</span><span class="n">result</span> <span class="o">/=</span> <span class="n">n</span><span class="p">);</span>
  704. <span class="p">}</span>
  705.  
  706. <span class="n">BigInteger</span> <span class="n">BigInteger</span><span class="o">::</span><span class="k">operator</span><span class="o">%</span> <span class="p">(</span><span class="n">ullong</span> <span class="n">n</span><span class="p">)</span> <span class="k">const</span> <span class="p">{</span>
  707.     <span class="n">BigInteger</span> <span class="n">result</span><span class="p">(</span><span class="o">*</span><span class="k">this</span><span class="p">);</span>
  708.     <span class="k">return</span> <span class="p">(</span><span class="n">result</span> <span class="o">/=</span> <span class="n">n</span><span class="p">);</span>
  709. <span class="p">}</span>
  710.  
  711. <span class="n">BigInteger</span> <span class="n">BigInteger</span><span class="o">::</span><span class="k">operator</span><span class="o">*</span> <span class="p">(</span><span class="k">const</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">bi</span><span class="p">)</span> <span class="k">const</span> <span class="p">{</span>
  712.     <span class="n">BigInteger</span> <span class="n">result</span><span class="p">(</span><span class="o">*</span><span class="k">this</span><span class="p">);</span>
  713.     <span class="k">return</span> <span class="p">(</span><span class="n">result</span>  <span class="o">*=</span> <span class="n">bi</span><span class="p">);</span>
  714. <span class="p">}</span>
  715.  
  716. <span class="n">BigInteger</span> <span class="n">BigInteger</span><span class="o">::</span><span class="k">operator</span><span class="o">&lt;&lt;</span> <span class="p">(</span><span class="n">ullong</span> <span class="n">n</span><span class="p">)</span> <span class="k">const</span> <span class="p">{</span>
  717.     <span class="n">BigInteger</span> <span class="n">result</span><span class="p">(</span><span class="o">*</span><span class="k">this</span><span class="p">);</span>
  718.     <span class="k">return</span> <span class="p">(</span><span class="n">result</span> <span class="o">&lt;&lt;=</span>  <span class="n">n</span><span class="p">);</span>
  719. <span class="p">}</span>
  720.  
  721. <span class="kt">bool</span> <span class="n">BigInteger</span><span class="o">::</span><span class="k">operator</span><span class="o">==</span> <span class="p">(</span><span class="k">const</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">other</span><span class="p">)</span> <span class="k">const</span> <span class="p">{</span>
  722.     <span class="k">return</span> <span class="k">this</span><span class="o">-&gt;</span><span class="n">digits</span> <span class="o">==</span> <span class="n">other</span><span class="p">.</span><span class="n">digits</span><span class="p">;</span>
  723. <span class="p">}</span>
  724.  
  725. <span class="kt">bool</span> <span class="n">BigInteger</span><span class="o">::</span><span class="k">operator</span><span class="o">==</span> <span class="p">(</span><span class="n">ullong</span> <span class="n">other</span><span class="p">)</span> <span class="k">const</span> <span class="p">{</span>
  726.     <span class="k">return</span> <span class="o">*</span><span class="k">this</span> <span class="o">==</span> <span class="n">BigInteger</span><span class="p">(</span><span class="n">other</span><span class="p">);</span>
  727. <span class="p">}</span>
  728.  
  729. <span class="kt">bool</span> <span class="n">BigInteger</span><span class="o">::</span><span class="k">operator</span><span class="o">&lt;</span> <span class="p">(</span><span class="k">const</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">other</span><span class="p">)</span> <span class="k">const</span> <span class="p">{</span>
  730.     <span class="k">if</span><span class="p">(</span><span class="n">digits</span><span class="p">.</span><span class="n">size</span><span class="p">()</span> <span class="o">&lt;</span> <span class="n">other</span><span class="p">.</span><span class="n">digits</span><span class="p">.</span><span class="n">size</span><span class="p">())</span>
  731.         <span class="k">return</span> <span class="kc">true</span><span class="p">;</span>
  732.     <span class="k">if</span><span class="p">(</span><span class="n">other</span><span class="p">.</span><span class="n">digits</span><span class="p">.</span><span class="n">size</span><span class="p">()</span> <span class="o">&lt;</span> <span class="n">digits</span><span class="p">.</span><span class="n">size</span><span class="p">())</span>
  733.         <span class="k">return</span> <span class="kc">false</span><span class="p">;</span>
  734.  
  735.     <span class="k">for</span><span class="p">(</span><span class="n">ullong</span> <span class="n">i</span> <span class="o">=</span> <span class="n">digits</span><span class="p">.</span><span class="n">size</span><span class="p">()</span><span class="o">-</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">;</span> <span class="o">--</span><span class="n">i</span><span class="p">)</span> <span class="p">{</span>
  736.         <span class="k">if</span><span class="p">(</span><span class="n">digits</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&lt;</span> <span class="n">other</span><span class="p">.</span><span class="n">digits</span><span class="p">[</span><span class="n">i</span><span class="p">])</span>
  737.             <span class="k">return</span> <span class="kc">true</span><span class="p">;</span>
  738.         <span class="k">if</span><span class="p">(</span><span class="n">other</span><span class="p">.</span><span class="n">digits</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&lt;</span> <span class="n">digits</span><span class="p">[</span><span class="n">i</span><span class="p">])</span>
  739.             <span class="k">return</span> <span class="kc">false</span><span class="p">;</span>
  740.     <span class="p">}</span>
  741.     <span class="k">return</span> <span class="n">digits</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">&lt;</span> <span class="n">other</span><span class="p">.</span><span class="n">digits</span><span class="p">[</span><span class="mi">0</span><span class="p">];</span>
  742. <span class="p">}</span>
  743.  
  744. <span class="kt">bool</span> <span class="n">BigInteger</span><span class="o">::</span><span class="k">operator</span><span class="o">&lt;</span> <span class="p">(</span><span class="n">ullong</span> <span class="n">other</span><span class="p">)</span> <span class="k">const</span> <span class="p">{</span>
  745.     <span class="k">return</span> <span class="o">*</span><span class="k">this</span> <span class="o">&lt;</span> <span class="n">BigInteger</span><span class="p">(</span><span class="n">other</span><span class="p">);</span>
  746. <span class="p">}</span>
  747.  
  748. <span class="kt">bool</span> <span class="n">BigInteger</span><span class="o">::</span><span class="k">operator</span><span class="o">&gt;</span> <span class="p">(</span><span class="k">const</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">other</span><span class="p">)</span> <span class="k">const</span> <span class="p">{</span>
  749.     <span class="k">return</span> <span class="p">(</span><span class="o">!</span><span class="p">(</span><span class="o">*</span><span class="k">this</span> <span class="o">&lt;</span> <span class="n">other</span><span class="p">));</span>
  750. <span class="p">}</span>
  751.  
  752. <span class="kt">bool</span> <span class="n">BigInteger</span><span class="o">::</span><span class="k">operator</span><span class="o">&gt;</span> <span class="p">(</span><span class="n">ullong</span> <span class="n">other</span><span class="p">)</span> <span class="k">const</span> <span class="p">{</span>
  753.     <span class="k">return</span> <span class="p">(</span><span class="o">*</span><span class="k">this</span> <span class="o">&gt;</span> <span class="n">BigInteger</span><span class="p">(</span><span class="n">other</span><span class="p">));</span>
  754. <span class="p">}</span>
  755.  
  756. <span class="kt">bool</span> <span class="n">BigInteger</span><span class="o">::</span><span class="k">operator</span><span class="o">&lt;=</span> <span class="p">(</span><span class="k">const</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">other</span><span class="p">)</span> <span class="k">const</span> <span class="p">{</span>
  757.     <span class="k">if</span><span class="p">(</span><span class="o">*</span><span class="k">this</span> <span class="o">&lt;</span> <span class="n">other</span><span class="p">)</span>
  758.         <span class="k">return</span> <span class="kc">true</span><span class="p">;</span>
  759.     <span class="k">if</span><span class="p">(</span><span class="o">*</span><span class="k">this</span> <span class="o">==</span> <span class="n">other</span><span class="p">)</span>
  760.         <span class="k">return</span> <span class="kc">true</span><span class="p">;</span>
  761.  
  762.     <span class="k">return</span> <span class="kc">false</span><span class="p">;</span>
  763. <span class="p">}</span>
  764.  
  765. <span class="kt">bool</span> <span class="n">BigInteger</span><span class="o">::</span><span class="k">operator</span><span class="o">&lt;=</span> <span class="p">(</span><span class="n">ullong</span> <span class="n">other</span><span class="p">)</span> <span class="k">const</span> <span class="p">{</span>
  766.     <span class="k">return</span> <span class="p">(</span><span class="o">*</span><span class="k">this</span> <span class="o">&lt;=</span> <span class="n">BigInteger</span><span class="p">(</span><span class="n">other</span><span class="p">));</span>
  767. <span class="p">}</span>
  768.  
  769. <span class="kt">bool</span> <span class="n">BigInteger</span><span class="o">::</span><span class="k">operator</span><span class="o">&gt;=</span> <span class="p">(</span><span class="k">const</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">other</span><span class="p">)</span> <span class="k">const</span> <span class="p">{</span>
  770.     <span class="k">if</span><span class="p">(</span><span class="o">*</span><span class="k">this</span> <span class="o">&gt;</span> <span class="n">other</span><span class="p">)</span>
  771.         <span class="k">return</span> <span class="kc">true</span><span class="p">;</span>
  772.     <span class="k">if</span><span class="p">(</span><span class="o">*</span><span class="k">this</span> <span class="o">==</span> <span class="n">other</span><span class="p">)</span>
  773.         <span class="k">return</span> <span class="kc">true</span><span class="p">;</span>
  774.     <span class="k">return</span> <span class="kc">false</span><span class="p">;</span>
  775. <span class="p">}</span>
  776.  
  777. <span class="kt">bool</span> <span class="n">BigInteger</span><span class="o">::</span><span class="k">operator</span><span class="o">&gt;=</span> <span class="p">(</span><span class="n">ullong</span> <span class="n">other</span><span class="p">)</span> <span class="k">const</span> <span class="p">{</span>
  778.     <span class="k">return</span> <span class="p">(</span><span class="o">*</span><span class="k">this</span> <span class="o">&gt;=</span> <span class="n">BigInteger</span><span class="p">(</span><span class="n">other</span><span class="p">));</span>
  779. <span class="p">}</span>
  780.  
  781. <span class="kt">bool</span> <span class="n">BigInteger</span><span class="o">::</span><span class="k">operator</span><span class="o">!=</span> <span class="p">(</span><span class="k">const</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">other</span><span class="p">)</span> <span class="k">const</span> <span class="p">{</span>
  782.     <span class="k">return</span> <span class="p">(</span><span class="o">!</span><span class="p">(</span><span class="o">*</span><span class="k">this</span> <span class="o">==</span> <span class="n">other</span><span class="p">));</span>
  783. <span class="p">}</span>
  784.  
  785. <span class="kt">bool</span> <span class="n">BigInteger</span><span class="o">::</span><span class="k">operator</span><span class="o">!=</span> <span class="p">(</span><span class="n">ullong</span> <span class="n">other</span><span class="p">)</span> <span class="k">const</span> <span class="p">{</span>
  786.     <span class="k">return</span> <span class="p">(</span><span class="o">*</span><span class="k">this</span> <span class="o">!=</span> <span class="n">BigInteger</span><span class="p">(</span><span class="n">other</span><span class="p">));</span>
  787. <span class="p">}</span>
  788.  
  789. <span class="kt">void</span> <span class="n">BigInteger</span><span class="o">::</span><span class="n">normalize</span><span class="p">()</span> <span class="p">{</span>
  790.     <span class="k">while</span> <span class="p">(</span><span class="n">digits</span><span class="p">.</span><span class="n">size</span><span class="p">()</span> <span class="o">&gt;</span> <span class="mi">1</span><span class="p">)</span> <span class="p">{</span>
  791.         <span class="k">if</span> <span class="p">(</span><span class="n">digits</span><span class="p">.</span><span class="n">back</span><span class="p">()</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span>
  792.             <span class="n">digits</span><span class="p">.</span><span class="n">pop_back</span><span class="p">();</span>
  793.         <span class="k">else</span>
  794.             <span class="k">break</span><span class="p">;</span>
  795.     <span class="p">}</span>
  796. <span class="p">}</span>
  797.  
  798. <span class="n">BigInteger</span> <span class="k">operator</span><span class="o">+</span> <span class="p">(</span><span class="n">ullong</span> <span class="n">n</span><span class="p">,</span> <span class="k">const</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">bi</span><span class="p">)</span> <span class="p">{</span>
  799.     <span class="k">return</span> <span class="n">bi</span> <span class="o">+</span> <span class="n">n</span><span class="p">;</span>
  800. <span class="p">}</span>
  801.  
  802. <span class="n">BigInteger</span> <span class="k">operator</span><span class="o">*</span> <span class="p">(</span><span class="n">ullong</span> <span class="n">n</span><span class="p">,</span> <span class="k">const</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">bi</span><span class="p">)</span> <span class="p">{</span>
  803.     <span class="k">return</span> <span class="n">bi</span> <span class="o">*</span> <span class="n">n</span><span class="p">;</span>
  804. <span class="p">}</span>
  805.  
  806. <span class="n">std</span><span class="o">::</span><span class="n">ostream</span><span class="o">&amp;</span> <span class="k">operator</span><span class="o">&lt;&lt;</span> <span class="p">(</span><span class="n">std</span><span class="o">::</span><span class="n">ostream</span><span class="o">&amp;</span> <span class="n">out</span><span class="p">,</span> <span class="k">const</span> <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">bi</span><span class="p">)</span> <span class="p">{</span>
  807.     <span class="n">BigInteger</span><span class="o">&amp;</span> <span class="n">bi2</span> <span class="o">=</span> <span class="k">const_cast</span><span class="o">&lt;</span><span class="n">BigInteger</span><span class="o">&amp;&gt;</span><span class="p">(</span><span class="n">bi</span><span class="p">);</span>
  808.     <span class="n">bi2</span><span class="p">.</span><span class="n">normalize</span><span class="p">();</span>
  809.  
  810.     <span class="kt">long</span> <span class="kt">long</span> <span class="n">size</span> <span class="o">=</span> <span class="n">bi</span><span class="p">.</span><span class="n">digits</span><span class="p">.</span><span class="n">size</span><span class="p">();</span>
  811.  
  812.     <span class="k">if</span> <span class="p">(</span><span class="n">bi</span><span class="p">.</span><span class="n">digits</span><span class="p">[</span><span class="n">size</span> <span class="o">-</span> <span class="mi">1</span><span class="p">])</span>
  813.         <span class="n">out</span> <span class="o">&lt;&lt;</span> <span class="n">bi</span><span class="p">.</span><span class="n">digits</span><span class="p">[</span><span class="n">size</span> <span class="o">-</span> <span class="mi">1</span><span class="p">];</span>
  814.  
  815.     <span class="k">for</span><span class="p">(</span><span class="kt">long</span> <span class="kt">long</span> <span class="n">i</span> <span class="o">=</span> <span class="n">size</span> <span class="o">-</span> <span class="mi">2</span><span class="p">;</span> <span class="n">i</span> <span class="o">&gt;=</span> <span class="mi">0</span><span class="p">;</span> <span class="o">--</span><span class="n">i</span><span class="p">)</span> <span class="p">{</span>
  816.         <span class="n">std</span><span class="o">::</span><span class="n">stringstream</span> <span class="n">buffer</span><span class="p">;</span>
  817.         <span class="n">buffer</span> <span class="o">&lt;&lt;</span> <span class="n">bi</span><span class="p">.</span><span class="n">digits</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
  818.  
  819.         <span class="n">std</span><span class="o">::</span><span class="n">string</span> <span class="n">str</span> <span class="o">=</span> <span class="n">buffer</span><span class="p">.</span><span class="n">str</span><span class="p">();</span>
  820.  
  821.         <span class="n">ullong</span> <span class="n">toN</span> <span class="o">=</span> <span class="n">BigInteger</span><span class="o">::</span><span class="n">N</span> <span class="o">-</span> <span class="n">str</span><span class="p">.</span><span class="n">size</span><span class="p">();</span>
  822.         <span class="k">if</span> <span class="p">(</span><span class="n">toN</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">)</span>
  823.             <span class="n">str</span> <span class="o">=</span> <span class="n">std</span><span class="o">::</span><span class="n">string</span><span class="p">(</span><span class="n">toN</span><span class="p">,</span> <span class="sc">'0'</span><span class="p">)</span> <span class="o">+</span> <span class="n">str</span><span class="p">;</span>
  824.  
  825.         <span class="n">out</span> <span class="o">&lt;&lt;</span> <span class="n">str</span><span class="p">;</span>
  826.     <span class="p">}</span>
  827.  
  828.     <span class="k">return</span> <span class="n">out</span><span class="p">;</span>
  829. <span class="p">}</span>
  830.  
  831. <span class="n">std</span><span class="o">::</span><span class="n">string</span> <span class="n">BigInteger</span><span class="o">::</span><span class="n">toString</span><span class="p">()</span> <span class="p">{</span>
  832.     <span class="n">std</span><span class="o">::</span><span class="n">stringstream</span> <span class="n">out</span><span class="p">;</span>
  833.     <span class="kt">long</span> <span class="kt">long</span> <span class="n">size</span> <span class="o">=</span> <span class="n">digits</span><span class="p">.</span><span class="n">size</span><span class="p">();</span>
  834.  
  835.     <span class="k">if</span> <span class="p">(</span><span class="n">digits</span><span class="p">[</span><span class="n">size</span> <span class="o">-</span> <span class="mi">1</span><span class="p">])</span>
  836.         <span class="n">out</span> <span class="o">&lt;&lt;</span> <span class="n">digits</span><span class="p">[</span><span class="n">size</span> <span class="o">-</span> <span class="mi">1</span><span class="p">];</span>
  837.  
  838.     <span class="k">for</span><span class="p">(</span><span class="kt">long</span> <span class="kt">long</span> <span class="n">i</span> <span class="o">=</span> <span class="n">size</span> <span class="o">-</span> <span class="mi">2</span><span class="p">;</span> <span class="n">i</span> <span class="o">&gt;=</span> <span class="mi">0</span><span class="p">;</span> <span class="o">--</span><span class="n">i</span><span class="p">)</span> <span class="p">{</span>
  839.         <span class="n">std</span><span class="o">::</span><span class="n">string</span> <span class="n">str</span> <span class="o">=</span> <span class="n">std</span><span class="o">::</span><span class="n">to_string</span><span class="p">(</span><span class="n">digits</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span>
  840.  
  841.         <span class="n">ullong</span> <span class="n">toN</span> <span class="o">=</span> <span class="n">BigInteger</span><span class="o">::</span><span class="n">N</span> <span class="o">-</span> <span class="n">str</span><span class="p">.</span><span class="n">size</span><span class="p">();</span>
  842.         <span class="k">if</span> <span class="p">(</span><span class="n">toN</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">)</span>
  843.             <span class="n">str</span> <span class="o">=</span> <span class="n">std</span><span class="o">::</span><span class="n">string</span><span class="p">(</span><span class="n">toN</span><span class="p">,</span> <span class="sc">'0'</span><span class="p">)</span> <span class="o">+</span> <span class="n">str</span><span class="p">;</span>
  844.  
  845.         <span class="n">out</span> <span class="o">&lt;&lt;</span> <span class="n">str</span><span class="p">;</span>
  846.     <span class="p">}</span>
  847.  
  848.     <span class="k">return</span> <span class="n">out</span><span class="p">.</span><span class="n">str</span><span class="p">();</span>
  849. <span class="p">}</span>
  850.  
  851. <span class="n">BigInteger</span> <span class="k">operator</span><span class="s">""</span> <span class="n">_Big</span><span class="p">(</span><span class="k">const</span> <span class="kt">char</span><span class="o">*</span> <span class="n">str</span><span class="p">,</span> <span class="n">std</span><span class="o">::</span><span class="n">size_t</span> <span class="n">n</span><span class="p">)</span> <span class="p">{</span>
  852.     <span class="k">return</span> <span class="n">BigInteger</span><span class="p">(</span><span class="n">std</span><span class="o">::</span><span class="n">string</span><span class="p">(</span><span class="n">str</span><span class="p">,</span><span class="n">n</span><span class="p">));</span>
  853. <span class="p">}</span>
  854.  
  855. <span class="n">BigInteger</span> <span class="k">operator</span><span class="s">""</span> <span class="n">_Big</span><span class="p">(</span><span class="n">ullong</span> <span class="n">number</span><span class="p">)</span> <span class="p">{</span>
  856.     <span class="k">return</span> <span class="n">BigInteger</span><span class="p">(</span><span class="n">number</span><span class="p">);</span>
  857. <span class="p">}</span>
  858.  
  859. <span class="n">BigInteger</span> <span class="n">bfactorial</span><span class="p">(</span><span class="n">ullong</span> <span class="n">n</span><span class="p">)</span> <span class="p">{</span>
  860.     <span class="k">static</span> <span class="n">std</span><span class="o">::</span><span class="n">map</span><span class="o">&lt;</span><span class="n">ullong</span><span class="p">,</span> <span class="n">BigInteger</span><span class="o">&gt;</span> <span class="n">cache</span><span class="p">;</span>
  861.     <span class="k">static</span> <span class="n">std</span><span class="o">::</span><span class="n">map</span><span class="o">&lt;</span><span class="n">ullong</span><span class="p">,</span> <span class="n">BigInteger</span><span class="o">&gt;::</span><span class="n">iterator</span> <span class="n">it</span><span class="p">;</span>
  862.  
  863.     <span class="k">if</span> <span class="p">(</span><span class="n">n</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span>
  864.         <span class="k">return</span> <span class="mi">1</span><span class="p">;</span>
  865.  
  866.     <span class="n">it</span> <span class="o">=</span> <span class="n">cache</span><span class="p">.</span><span class="n">find</span><span class="p">(</span><span class="n">n</span><span class="p">);</span>
  867.  
  868.     <span class="k">if</span> <span class="p">(</span><span class="n">it</span> <span class="o">!=</span> <span class="n">cache</span><span class="p">.</span><span class="n">end</span><span class="p">())</span>
  869.         <span class="k">return</span> <span class="n">it</span><span class="o">-&gt;</span><span class="n">second</span><span class="p">;</span>
  870.     <span class="k">else</span>
  871.         <span class="k">return</span> <span class="n">cache</span><span class="p">[</span><span class="n">n</span><span class="p">]</span> <span class="o">=</span> <span class="n">n</span> <span class="o">*</span> <span class="n">fact</span><span class="p">(</span><span class="n">n</span> <span class="o">-</span> <span class="mi">1</span><span class="p">);</span>
  872. <span class="p">}</span>
  873.  
  874. <span class="n">BigInteger</span> <span class="n">bfibonacci</span><span class="p">(</span><span class="n">ullong</span> <span class="n">n</span><span class="p">)</span> <span class="p">{</span>
  875.     <span class="k">static</span> <span class="n">std</span><span class="o">::</span><span class="n">map</span><span class="o">&lt;</span><span class="n">ullong</span><span class="p">,</span> <span class="n">BigInteger</span><span class="o">&gt;</span> <span class="n">cache</span><span class="p">;</span>
  876.     <span class="k">static</span> <span class="n">std</span><span class="o">::</span><span class="n">map</span><span class="o">&lt;</span><span class="n">ullong</span><span class="p">,</span> <span class="n">BigInteger</span><span class="o">&gt;::</span><span class="n">iterator</span> <span class="n">it</span><span class="p">;</span>
  877.  
  878.     <span class="k">if</span><span class="p">(</span><span class="n">n</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span>
  879.         <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
  880.     <span class="k">if</span><span class="p">(</span><span class="n">n</span> <span class="o">==</span> <span class="mi">1</span><span class="p">)</span>
  881.         <span class="k">return</span> <span class="mi">1</span><span class="p">;</span>
  882.  
  883.     <span class="n">it</span> <span class="o">=</span> <span class="n">cache</span><span class="p">.</span><span class="n">find</span><span class="p">(</span><span class="n">n</span><span class="p">);</span>
  884.  
  885.     <span class="k">if</span><span class="p">(</span><span class="n">it</span> <span class="o">!=</span> <span class="n">cache</span><span class="p">.</span><span class="n">end</span><span class="p">())</span>
  886.         <span class="k">return</span> <span class="n">it</span><span class="o">-&gt;</span><span class="n">second</span><span class="p">;</span>
  887.     <span class="k">else</span>
  888.         <span class="k">return</span> <span class="n">cache</span><span class="p">[</span><span class="n">n</span><span class="p">]</span> <span class="o">=</span> <span class="n">fibonacci</span><span class="p">(</span><span class="n">n</span><span class="o">-</span><span class="mi">1</span><span class="p">)</span> <span class="o">+</span> <span class="n">fibonacci</span><span class="p">(</span><span class="n">n</span><span class="o">-</span><span class="mi">2</span><span class="p">);</span>
  889. <span class="p">}</span>
  890. <span class="p">}</span> <span class="c1">//namespace gears</span>
  891.  
  892. <span class="cp">#endif </span><span class="c1">//GEARS_BIG_INTEGER_HPP</span>
  893.  
  894. </pre></div></body>
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!