fork download
  1. #include <algorithm>
  2. #include <cstdlib>
  3. #include <iostream>
  4. #include <memory>
  5. #include <string>
  6. #include <vector>
  7.  
  8. using namespace std;
  9.  
  10. class UBigInt {
  11. public:
  12. UBigInt(const bool& bit = false);
  13. UBigInt(const shared_ptr<vector<bool> >& bits);
  14. UBigInt(const unsigned long& val);
  15. UBigInt operator +(const UBigInt& ade) const;
  16. UBigInt operator -(const UBigInt& sub) const;
  17. UBigInt operator *(const UBigInt& mer) const;
  18. UBigInt operator /(const UBigInt& dsr) const;
  19. UBigInt operator %(const UBigInt& nrm) const;
  20. UBigInt operator <<(const size_t& wid) const;
  21. UBigInt operator >>(const size_t& wid) const;
  22. UBigInt& operator =(const UBigInt& num);
  23. UBigInt& operator +=(const UBigInt& ade);
  24. UBigInt& operator -=(const UBigInt& sub);
  25. UBigInt& operator *=(const UBigInt& mer);
  26. UBigInt& operator /=(const UBigInt& dsr);
  27. UBigInt& operator %=(const UBigInt& nrm);
  28. UBigInt& operator <<=(const size_t& wid);
  29. UBigInt& operator >>=(const size_t& wid);
  30. bool operator ==(const UBigInt& num) const;
  31. bool operator <(const UBigInt& num) const;
  32. bool operator >(const UBigInt& num) const;
  33. bool operator !=(const UBigInt& num) const;
  34. bool operator <=(const UBigInt& num) const;
  35. bool operator >=(const UBigInt& num) const;
  36. UBigInt power(const UBigInt& exp);
  37. UBigInt modPower(const UBigInt& exp, const UBigInt& nrm);
  38. bool isZero() const;
  39. bool getLowestBit() const;
  40. unsigned long getLowestDWord() const;
  41. string toString(const unsigned int& base = 10) const;
  42. static UBigInt fromString(const string& str, const unsigned int& base = 10);
  43. protected:
  44. shared_ptr<vector<bool> > bits;
  45. static shared_ptr<vector<bool> > makeBits(const unsigned long& val);
  46. static shared_ptr<vector<bool> > add(const shared_ptr<vector<bool> >& age, const shared_ptr<vector<bool> >& ade);
  47. static shared_ptr<vector<bool> > subtract(const shared_ptr<vector<bool> >& min, const shared_ptr<vector<bool> >& sub);
  48. static shared_ptr<vector<bool> > multiply(const shared_ptr<vector<bool> >& mca, const shared_ptr<vector<bool> >& mer);
  49. static shared_ptr<vector<bool> > divide(const shared_ptr<vector<bool> >& dde, const shared_ptr<vector<bool> >& dsr, shared_ptr<vector<bool> >* rem = NULL);
  50. static shared_ptr<vector<bool> > leftShift(const shared_ptr<vector<bool> >& bits, const size_t& wid);
  51. static shared_ptr<vector<bool> > rightShift(const shared_ptr<vector<bool> >& bits, const size_t& wid);
  52. static bool less(const shared_ptr<vector<bool> >& left, const shared_ptr<vector<bool> >& right);
  53. static bool equal(const shared_ptr<vector<bool> >& left, const shared_ptr<vector<bool> >& right);
  54. static bool isZero(const shared_ptr<vector<bool> >& bits);
  55. static unsigned long getLowestDWord(const shared_ptr<vector<bool> >& bits);
  56. static unsigned int charToFigure(const char& ch);
  57. static char figureToChar(const unsigned int& fig);
  58. static shared_ptr<vector<bool> > trim(const shared_ptr<vector<bool> >& bits);
  59. };
  60.  
  61. #define ASSERT(pred) assert(#pred, pred);
  62.  
  63. extern void assert(const char* pred_str, const bool& pred);
  64.  
  65. UBigInt::UBigInt(const bool& bit) : bits(new vector<bool>(1, bit)) {}
  66.  
  67. UBigInt::UBigInt(const shared_ptr<vector<bool> >& bits) : bits(bits) {}
  68.  
  69. UBigInt::UBigInt(const unsigned long& val) : bits(makeBits(val)) {}
  70.  
  71. UBigInt UBigInt::operator +(const UBigInt& ade) const {
  72. return UBigInt(add(this->bits, ade.bits));
  73. }
  74.  
  75. UBigInt UBigInt::operator -(const UBigInt& sub) const {
  76. return UBigInt(subtract(this->bits, sub.bits));
  77. }
  78.  
  79. UBigInt UBigInt::operator *(const UBigInt& mer) const {
  80. return UBigInt(multiply(this->bits, mer.bits));
  81. }
  82.  
  83. UBigInt UBigInt::operator /(const UBigInt& dsr) const {
  84. return UBigInt(divide(this->bits, dsr.bits));
  85. }
  86.  
  87. UBigInt UBigInt::operator %(const UBigInt& nrm) const {
  88. shared_ptr<vector<bool> > rem;
  89. divide(this->bits, nrm.bits, &rem);
  90. return UBigInt(rem);
  91. }
  92.  
  93. UBigInt UBigInt::operator <<(const size_t& wid) const {
  94. return UBigInt(leftShift(this->bits, wid));
  95. }
  96.  
  97. UBigInt UBigInt::operator >>(const size_t& wid) const {
  98. return UBigInt(rightShift(this->bits, wid));
  99. }
  100.  
  101. UBigInt& UBigInt::operator =(const UBigInt& num) {
  102. this->bits = shared_ptr<vector<bool> >(new vector<bool>(*num.bits));
  103. return *this;
  104. }
  105.  
  106. UBigInt& UBigInt::operator +=(const UBigInt& add) {
  107. return *this = *this + add;
  108. }
  109.  
  110. UBigInt& UBigInt::operator -=(const UBigInt& sub) {
  111. return *this = *this - sub;
  112. }
  113.  
  114. UBigInt& UBigInt::operator *=(const UBigInt& mer) {
  115. return *this = *this * mer;
  116. }
  117.  
  118. UBigInt& UBigInt::operator /=(const UBigInt& dsr) {
  119. return *this = *this / dsr;
  120. }
  121.  
  122. UBigInt& UBigInt::operator %=(const UBigInt& nrm) {
  123. return *this = *this % nrm;
  124. }
  125.  
  126. UBigInt& UBigInt::operator <<=(const size_t& wid) {
  127. return *this = *this << wid;
  128. }
  129.  
  130. UBigInt& UBigInt::operator >>=(const size_t& wid) {
  131. return *this = *this >> wid;
  132. }
  133.  
  134. bool UBigInt::operator ==(const UBigInt& num) const {
  135. return equal(this->bits, num.bits);
  136. }
  137.  
  138. bool UBigInt::operator <(const UBigInt& num) const {
  139. return less(this->bits, num.bits);
  140. }
  141.  
  142. bool UBigInt::operator >(const UBigInt& num) const {
  143. return !equal(this->bits, num.bits) && !less(this->bits, num.bits);
  144. }
  145.  
  146. bool UBigInt::operator !=(const UBigInt& num) const {
  147. return !equal(this->bits, num.bits);
  148. }
  149.  
  150. bool UBigInt::operator <=(const UBigInt& num) const {
  151. return equal(this->bits, num.bits) || less(this->bits, num.bits);
  152. }
  153.  
  154. bool UBigInt::operator >=(const UBigInt& num) const {
  155. return !less(this->bits, num.bits);
  156. }
  157.  
  158. UBigInt UBigInt::power(const UBigInt& exp) {
  159. if (isZero()) return UBigInt(false);
  160. UBigInt res(true);
  161. UBigInt mod = *this;
  162. for (UBigInt exp2 = exp;;) {
  163. if (exp2.getLowestBit()) {
  164. res = (res * mod);
  165. }
  166. exp2 >>= 1;
  167. if (exp2.isZero()) break;
  168. mod = (mod * mod);
  169. }
  170. return res;
  171. }
  172.  
  173. UBigInt UBigInt::modPower(const UBigInt& exp, const UBigInt& nrm) {
  174. if (nrm.isZero()) throw string("法がゼロ。");
  175. if (isZero()) return UBigInt(false);
  176. UBigInt res(true);
  177. UBigInt mod = *this % nrm;
  178. for (UBigInt exp2 = exp;;) {
  179. if (exp2.getLowestBit()) {
  180. res = (res * mod) % nrm;
  181. }
  182. exp2 >>= 1;
  183. if (exp2.isZero()) break;
  184. mod = (mod * mod) % nrm;
  185. }
  186. return res;
  187. }
  188.  
  189. bool UBigInt::isZero() const {
  190. return isZero(this->bits);
  191. }
  192.  
  193. bool UBigInt::getLowestBit() const {
  194. return this->bits->back();
  195. }
  196.  
  197. unsigned long UBigInt::getLowestDWord() const {
  198. return getLowestDWord(this->bits);
  199. }
  200.  
  201. string UBigInt::toString(const unsigned int& base) const {
  202. string res;
  203. shared_ptr<vector<bool> > wrk = this->bits;
  204. shared_ptr<vector<bool> > base_bits(makeBits(base));
  205. while (!isZero(wrk)) {
  206. shared_ptr<vector<bool> > rem;
  207. wrk = divide(wrk, base_bits, &rem);
  208. res += figureToChar(getLowestDWord(rem));
  209. }
  210. if (res.empty()) res += '0';
  211. reverse(res.begin(), res.end());
  212. return res;
  213. }
  214.  
  215. UBigInt UBigInt::fromString(const string& str, const unsigned int& base) {
  216. shared_ptr<vector<bool> > bits(new vector<bool>(1, false));
  217. shared_ptr<vector<bool> > base_bits(makeBits(base));
  218. for (string::const_iterator iter = str.begin(); iter != str.end(); iter++) {
  219. if (iter != str.begin()) bits = multiply(bits, base_bits);
  220. unsigned int fig = charToFigure(*iter);
  221. if (fig >= base) throw string("値が範囲を逸脱している。");
  222. bits = add(bits, makeBits(fig));
  223. }
  224. return UBigInt(bits);
  225. }
  226.  
  227. shared_ptr<vector<bool> > UBigInt::makeBits(const unsigned long& val) {
  228. shared_ptr<vector<bool> > res(new vector<bool>);
  229. for (int i = 31; i >= 0; i--) {
  230. if ((val >> i) & 1) res->push_back(true);
  231. else if (!res->empty()) res->push_back(false);
  232. }
  233. if (res->empty()) res->push_back(false);
  234. return res;
  235. }
  236.  
  237. shared_ptr<vector<bool> > UBigInt::add(const shared_ptr<vector<bool> >& age, const shared_ptr<vector<bool> >& ade) {
  238. shared_ptr<vector<bool> > sum(new vector<bool>);
  239. vector<bool>::const_reverse_iterator age_iter = age->rbegin();
  240. vector<bool>::const_reverse_iterator ade_iter = ade->rbegin();
  241. bool carry = false;
  242. while (age_iter != age->rend() || ade_iter != ade->rend()) {
  243. int age_val = age_iter != age->rend() ? int(*age_iter) : 0;
  244. int ade_val = ade_iter != ade->rend() ? int(*ade_iter) : 0;
  245. int sum_val = age_val + ade_val + int(carry);
  246. carry = sum_val > 1;
  247. if (carry) sum_val -= 2;
  248. sum->push_back(sum_val == 1);
  249. if (age_iter != age->rend()) age_iter++;
  250. if (ade_iter != ade->rend()) ade_iter++;
  251. }
  252. if (carry) sum->push_back(true);
  253. if (sum->empty()) sum->push_back(false);
  254. reverse(sum->begin(), sum->end());
  255. return sum;
  256. }
  257.  
  258. shared_ptr<vector<bool> > UBigInt::subtract(const shared_ptr<vector<bool> >& min, const shared_ptr<vector<bool> >& sub) {
  259. shared_ptr<vector<bool> > dif(new vector<bool>);
  260. vector<bool>::const_reverse_iterator min_iter = min->rbegin();
  261. vector<bool>::const_reverse_iterator sub_iter = sub->rbegin();
  262. bool borrow = false;
  263. while (min_iter != min->rend() || sub_iter != sub->rend()) {
  264. int min_val = min_iter != min->rend() ? int(*min_iter) : 0;
  265. int sub_val = sub_iter != sub->rend() ? int(*sub_iter) : 0;
  266. int dif_val = min_val - sub_val - int(borrow);
  267. borrow = dif_val < 0;
  268. if (borrow) dif_val += 2;
  269. dif->push_back(dif_val == 1);
  270. if (min_iter != min->rend()) min_iter++;
  271. if (sub_iter != sub->rend()) sub_iter++;
  272. }
  273. if (borrow) throw string("被減数が減数より小さい。");
  274. reverse(dif->begin(), dif->end());
  275. return trim(dif);
  276. }
  277.  
  278. shared_ptr<vector<bool> > UBigInt::multiply(const shared_ptr<vector<bool> >& mca, const shared_ptr<vector<bool> >& mer) {
  279. shared_ptr<vector<bool> > pro(new vector<bool>(1, false));
  280. vector<bool>::const_reverse_iterator mer_iter = mer->rbegin();
  281. size_t wid = 0;
  282. while (mer_iter != mer->rend()) {
  283. if (*mer_iter) pro = add(pro, leftShift(mca, wid));
  284. mer_iter++;
  285. wid++;
  286. }
  287. return pro;
  288. }
  289.  
  290. shared_ptr<vector<bool> > UBigInt::divide(const shared_ptr<vector<bool> >& dde, const shared_ptr<vector<bool> >& dsr, shared_ptr<vector<bool> >* rem) {
  291. if (isZero(dsr)) throw string("除数がゼロ。");
  292. shared_ptr<vector<bool> > quo(new vector<bool>);
  293. shared_ptr<vector<bool> > fld(new vector<bool>);
  294. for (vector<bool>::const_iterator dde_iter = dde->begin(); dde_iter != dde->end(); dde_iter++) {
  295. fld->push_back(*dde_iter);
  296. fld = trim(fld);
  297. if (!less(fld, dsr)) {
  298. quo->push_back(true);
  299. fld = subtract(fld, dsr);
  300. }
  301. else if (!quo->empty()) quo->push_back(false);
  302. }
  303. if (quo->empty()) quo->push_back(false);
  304. if (rem) *rem = fld;
  305. return quo;
  306. }
  307.  
  308. shared_ptr<vector<bool> > UBigInt::leftShift(const shared_ptr<vector<bool> >& bits, const size_t& wid) {
  309. shared_ptr<vector<bool> > res(new vector<bool>(*bits));
  310. for (int i = 0; i < wid; i++) res->push_back(false);
  311. return res;
  312. }
  313.  
  314. shared_ptr<vector<bool> > UBigInt::rightShift(const shared_ptr<vector<bool> >& bits, const size_t& wid) {
  315. shared_ptr<vector<bool> > res;
  316. if (wid < bits->size()) res = shared_ptr<vector<bool> >(new vector<bool>(bits->begin(), bits->end() - wid));
  317. else res = shared_ptr<vector<bool> >(new vector<bool>(1, false));
  318. return res;
  319. }
  320.  
  321. bool UBigInt::equal(const shared_ptr<vector<bool> >& left, const shared_ptr<vector<bool> >& right) {
  322. bool res;
  323. if (left->size() != right->size()) res = false;
  324. else {
  325. vector<bool>::const_iterator left_iter = left->begin();
  326. vector<bool>::const_iterator right_iter = right->begin();
  327. for (;;) {
  328. if (left_iter == left->end()) {
  329. res = true;
  330. break;
  331. }
  332. else if (!*left_iter && *right_iter) {
  333. res = false;
  334. break;
  335. }
  336. else if (*left_iter && !*right_iter) {
  337. res = false;
  338. break;
  339. }
  340. left_iter++;
  341. right_iter++;
  342. }
  343. }
  344. return res;
  345. }
  346.  
  347. bool UBigInt::less(const shared_ptr<vector<bool> >& left, const shared_ptr<vector<bool> >& right) {
  348. bool res;
  349. if (left->size() < right->size()) res = true;
  350. else if (left->size() > right->size()) res = false;
  351. else {
  352. vector<bool>::const_iterator left_iter = left->begin();
  353. vector<bool>::const_iterator right_iter = right->begin();
  354. for (;;) {
  355. if (left_iter == left->end()) {
  356. res = false;
  357. break;
  358. }
  359. else if (!*left_iter && *right_iter) {
  360. res = true;
  361. break;
  362. }
  363. else if (*left_iter && !*right_iter) {
  364. res = false;
  365. break;
  366. }
  367. left_iter++;
  368. right_iter++;
  369. }
  370. }
  371. return res;
  372. }
  373.  
  374. bool UBigInt::isZero(const shared_ptr<vector<bool> >& bits) {
  375. return bits->size() == 1 && bits->front() == false;
  376. }
  377.  
  378. unsigned long UBigInt::getLowestDWord(const shared_ptr<vector<bool> >& bits) {
  379. unsigned long res = 0;
  380. vector<bool>::const_iterator iter = bits->begin();
  381. for (int i = 0; i < 32; i++) {
  382. if (iter == bits->end()) break;
  383. if (i != 0) res <<= 1;
  384. res |= int(*iter);
  385. iter++;
  386. }
  387. return res;
  388. }
  389.  
  390. unsigned int UBigInt::charToFigure(const char& ch) {
  391. unsigned int res;
  392. if (ch >= '0' && ch <= '9') res = ch - '0';
  393. else if (ch >= 'A' && ch <= 'Z') res = 10 + ch - 'A';
  394. else if (ch >= 'a' && ch <= 'z') res = 10 + ch - 'a';
  395. else throw string("文字が数ではない。");
  396. return res;
  397. }
  398.  
  399. char UBigInt::figureToChar(const unsigned int& fig) {
  400. char res;
  401. if (fig >= 0 && fig <= 9) res = '0' + fig;
  402. else if (fig >= 10 && fig <= 36) res = 'A' + (fig - 10);
  403. else throw string("値が範囲を逸脱している。");
  404. return res;
  405. }
  406.  
  407. shared_ptr<vector<bool> > UBigInt::trim(const shared_ptr<vector<bool> >& bits) {
  408. size_t pos = 0;
  409. while (pos != bits->size() && bits->at(pos) == false) pos++;
  410. if (pos == bits->size()) pos--;
  411. return shared_ptr<vector<bool> >(new vector<bool>(bits->begin() + pos, bits->end()));
  412. }
  413.  
  414. void assert(const char* pred_str, const bool& pred) {
  415. if (pred) {
  416. cout << "アサート成功: " << pred_str << endl;
  417. }
  418. else {
  419. cerr << "アサート失敗: " << pred_str << endl;
  420. exit(1);
  421. }
  422. }
  423.  
  424. int main() {
  425. try {
  426. ASSERT(UBigInt::fromString("0").power(UBigInt::fromString("4")) == UBigInt::fromString("0"))
  427. ASSERT(UBigInt::fromString("0").modPower(UBigInt::fromString("4"), UBigInt::fromString("10")) == UBigInt::fromString("0"))
  428. ASSERT(UBigInt::fromString("1").power(UBigInt::fromString("4")) == UBigInt::fromString("1"))
  429. ASSERT(UBigInt::fromString("1").modPower(UBigInt::fromString("4"), UBigInt::fromString("10")) == UBigInt::fromString("1"))
  430. ASSERT(UBigInt::fromString("2").power(UBigInt::fromString("4")) == UBigInt::fromString("16"))
  431. ASSERT(UBigInt::fromString("2").modPower(UBigInt::fromString("4"), UBigInt::fromString("10")) == UBigInt::fromString("6"))
  432. ASSERT(UBigInt::fromString("12").power(UBigInt::fromString("34")) == UBigInt::fromString("4922235242952026704037113243122008064"))
  433. ASSERT(UBigInt::fromString("12").modPower(UBigInt::fromString("34"), UBigInt::fromString("100")) == UBigInt::fromString("64"))
  434. ASSERT(UBigInt::fromString("2").modPower(UBigInt::fromString("4099"), UBigInt::fromString("100")) == UBigInt::fromString("88"))
  435. }
  436. catch (const string& msg) {
  437. cerr << msg << endl;
  438. return 1;
  439. }
  440. return 0;
  441. }
  442.  
Success #stdin #stdout 0s 3020KB
stdin
Standard input is empty
stdout
アサート成功: UBigInt::fromString("0").power(UBigInt::fromString("4")) == UBigInt::fromString("0")
アサート成功: UBigInt::fromString("0").modPower(UBigInt::fromString("4"), UBigInt::fromString("10")) == UBigInt::fromString("0")
アサート成功: UBigInt::fromString("1").power(UBigInt::fromString("4")) == UBigInt::fromString("1")
アサート成功: UBigInt::fromString("1").modPower(UBigInt::fromString("4"), UBigInt::fromString("10")) == UBigInt::fromString("1")
アサート成功: UBigInt::fromString("2").power(UBigInt::fromString("4")) == UBigInt::fromString("16")
アサート成功: UBigInt::fromString("2").modPower(UBigInt::fromString("4"), UBigInt::fromString("10")) == UBigInt::fromString("6")
アサート成功: UBigInt::fromString("12").power(UBigInt::fromString("34")) == UBigInt::fromString("4922235242952026704037113243122008064")
アサート成功: UBigInt::fromString("12").modPower(UBigInt::fromString("34"), UBigInt::fromString("100")) == UBigInt::fromString("64")
アサート成功: UBigInt::fromString("2").modPower(UBigInt::fromString("4099"), UBigInt::fromString("100")) == UBigInt::fromString("88")