fork download
copy 
  1. #include <algorithm>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <ctime>
  5. #include <iomanip>
  6. #include <iostream>
  7. #include <memory>
  8. #include <string>
  9.  
  10. using namespace std;
  11.  
  12. class UBigInt;
  13. class BitField;
  14.  
  15. extern bool primalityTestMillerRabin(const UBigInt& p, const unsigned int& cnt = 100);
  16.  
  17. class UBigInt {
  18. public:
  19.     typedef shared_ptr<BitField> BFPtr;
  20. 	static UBigInt fromString(const string& str, const unsigned int& base = 10);
  21. 	UBigInt(const unsigned int& num = 0);
  22. 	UBigInt(const BFPtr& fld);
  23. 	UBigInt(const UBigInt& num);
  24. 	UBigInt operator +(const UBigInt& ade) const;
  25. 	UBigInt operator -(const UBigInt& sub) const;
  26. 	UBigInt operator *(const UBigInt& mer) const;
  27. 	UBigInt operator /(const UBigInt& dsr) const;
  28. 	UBigInt operator %(const UBigInt& nrm) const;
  29. 	UBigInt operator <<(const size_t& wid) const;
  30. 	UBigInt operator >>(const size_t& wid) const;
  31. 	UBigInt& operator =(const UBigInt& num);
  32. 	UBigInt& operator +=(const UBigInt& ade);
  33. 	UBigInt& operator -=(const UBigInt& sub);
  34. 	UBigInt& operator *=(const UBigInt& mer);
  35. 	UBigInt& operator /=(const UBigInt& dsr);
  36. 	UBigInt& operator %=(const UBigInt& nrm);
  37. 	UBigInt& operator <<=(const unsigned int& wid);
  38. 	UBigInt& operator >>=(const unsigned int& wid);
  39. 	UBigInt& operator ++();
  40. 	UBigInt operator ++(int);
  41. 	UBigInt& operator --();
  42. 	UBigInt operator --(int);
  43. 	bool operator ==(const UBigInt& num) const;
  44. 	bool operator <(const UBigInt& num) const;
  45. 	bool operator >(const UBigInt& num) const;
  46. 	bool operator !=(const UBigInt& num) const;
  47. 	bool operator <=(const UBigInt& num) const;
  48. 	bool operator >=(const UBigInt& num) const;
  49. 	UBigInt power(const UBigInt& exp);
  50. 	UBigInt modPower(const UBigInt& exp, const UBigInt& nrm);
  51. 	bool isZero() const;
  52. 	bool getLSBit() const;
  53. 	unsigned int getLSInt() const;
  54. 	string toString(const unsigned int& base = 10) const;
  55. protected:
  56. 	BFPtr fld;
  57. 	static BFPtr add(const BFPtr& age, const BFPtr& ade);
  58. 	static BFPtr subtract(const BFPtr& min, const BFPtr& sub);
  59. 	static BFPtr multiply(const BFPtr& mca, const BFPtr& mer);
  60. 	static BFPtr divide(const BFPtr& dde, const BFPtr& dsr, BFPtr* rem = NULL);
  61. 	static unsigned int charToFigure(const char& ch);
  62. 	static char figureToChar(const unsigned int& fig);
  63. };
  64.  
  65. class BitField {
  66. public:
  67. 	BitField();
  68. 	BitField(const unsigned int& num);
  69. 	BitField(const BitField& fld);
  70. 	virtual ~BitField();
  71. 	BitField& operator =(const BitField& fld);
  72. 	bool operator ==(const BitField& fld) const;
  73. 	bool operator <(const BitField& fld) const;
  74. 	bool operator >(const BitField& fld) const;
  75. 	bool operator !=(const BitField& fld) const;
  76. 	bool operator <=(const BitField& fld) const;
  77. 	bool operator >=(const BitField& fld) const;
  78. 	unsigned int getWidth() const;
  79. 	bool isEmpty() const;
  80. 	bool isZero() const;
  81. 	bool getBit(const unsigned int& pos) const;
  82. 	bool getLSBit() const;
  83. 	bool getMSBit() const;
  84. 	unsigned int getLSInt() const;
  85. 	void setBit(const unsigned int& pos, const bool& bit);
  86. 	void pushMSBit(const bool& bit);
  87. 	void pushLSBit(const bool& bit);
  88. 	void shift(const int& wid);
  89. 	void trim();
  90. 	void clear();
  91. 	string toString() const;
  92. protected:
  93. 	unsigned char* buf;
  94. 	unsigned int buf_sz;
  95. 	int beg;
  96. 	unsigned int wid;
  97. 	int compare(const BitField& fld) const;
  98. 	void extendIfNecessary(const int& wid);
  99. };
  100.  
  101. #define ASSERT(pred) assert(#pred, pred);
  102.  
  103. extern void assert(const char* pred_str, const bool& pred);
  104.  
  105. bool primalityTestMillerRabin(const UBigInt& p, const unsigned int& cnt) {
  106. 	bool res;
  107. 	if (p == 1) res = false;
  108. 	else if (p == 2) res = true;
  109. 	else if (p.getLSBit() == false) res = false;
  110. 	else {
  111. 		UBigInt o = p - 1;
  112. 		UBigInt q = o;
  113. 		UBigInt k(1);
  114. 		while (q.getLSBit() == false) {
  115. 			q >>= 1;
  116. 			k++;
  117. 		}
  118. 		UBigInt a(2);
  119. 		UBigInt gap((o - 2) / cnt);
  120. 		if (gap.isZero()) gap++;
  121. 		for (; a < p; a += gap) {
  122. 			UBigInt b = a.modPower(q, p);
  123. 			if (b != 1 && b != o) {
  124. 				UBigInt i(1);
  125. 				for (; i < k; i++) {
  126. 					b = (b * b) % p;
  127. 					if (b == 1 || b == o) break;
  128. 				}
  129. 				if (i == k) {
  130. 					res = false;
  131. 					break;
  132. 				}
  133. 			}
  134. 		}
  135. 		if (a >= p) res = true;
  136. 	}
  137. 	return res;
  138. }
  139.  
  140. UBigInt UBigInt::fromString(const string& str, const unsigned int& base) {
  141. 	BFPtr fld(new BitField);
  142. 	BFPtr base_fld(new BitField(base));
  143. 	for (string::const_iterator iter = str.begin(); iter != str.end(); iter++) {
  144. 		if (iter != str.begin()) fld = multiply(fld, base_fld);
  145. 		unsigned int fig = charToFigure(*iter);
  146. 		if (fig >= base) throw string("値が範囲を逸脱している。");
  147. 		fld = add(fld, BFPtr(new BitField(fig)));
  148. 	}
  149. 	if (fld->isEmpty()) fld->pushMSBit(true);
  150. 	return UBigInt(fld);
  151. }
  152.  
  153. UBigInt::UBigInt(const unsigned int& num) : fld(new BitField(num)) {}
  154.  
  155. UBigInt::UBigInt(const BFPtr& fld) : fld(fld) {}
  156.  
  157. UBigInt::UBigInt(const UBigInt& num) : fld(new BitField(*num.fld)) {}
  158.  
  159. UBigInt UBigInt::operator +(const UBigInt& ade) const {
  160. 	return UBigInt(add(this->fld, ade.fld));
  161. }
  162.  
  163. UBigInt UBigInt::operator -(const UBigInt& sub) const {
  164. 	return UBigInt(subtract(this->fld, sub.fld));
  165. }
  166.  
  167. UBigInt UBigInt::operator *(const UBigInt& mer) const {
  168. 	return UBigInt(multiply(this->fld, mer.fld));
  169. }
  170.  
  171. UBigInt UBigInt::operator /(const UBigInt& dsr) const {
  172. 	return UBigInt(divide(this->fld, dsr.fld));
  173. }
  174.  
  175. UBigInt UBigInt::operator %(const UBigInt& nrm) const {
  176. 	if (nrm.isZero()) throw string("法がゼロ。");
  177. 	BFPtr rem;
  178. 	divide(this->fld, nrm.fld, &rem);
  179. 	return UBigInt(rem);
  180. }
  181.  
  182. UBigInt UBigInt::operator <<(const unsigned int& wid) const {
  183. 	BFPtr fld(new BitField(*this->fld));
  184. 	fld->shift(wid);
  185. 	return UBigInt(fld);
  186. }
  187.  
  188. UBigInt UBigInt::operator >>(const unsigned int& wid) const {
  189. 	BFPtr fld(new BitField(*this->fld));
  190. 	fld->shift(-wid);
  191. 	return UBigInt(fld);
  192. }
  193.  
  194. UBigInt& UBigInt::operator =(const UBigInt& num) {
  195. 	this->fld = BFPtr(new BitField(*num.fld));
  196. 	return *this;
  197. }
  198.  
  199. UBigInt& UBigInt::operator +=(const UBigInt& add) {
  200. 	return *this = *this + add;
  201. }
  202.  
  203. UBigInt& UBigInt::operator -=(const UBigInt& sub) {
  204. 	return *this = *this - sub;
  205. }
  206.  
  207. UBigInt& UBigInt::operator *=(const UBigInt& mer) {
  208. 	return *this = *this * mer;
  209. }
  210.  
  211. UBigInt& UBigInt::operator /=(const UBigInt& dsr) {
  212. 	return *this = *this / dsr;
  213. }
  214.  
  215. UBigInt& UBigInt::operator %=(const UBigInt& nrm) {
  216. 	return *this = *this % nrm;
  217. }
  218.  
  219. UBigInt& UBigInt::operator <<=(const size_t& wid) {
  220. 	return *this = *this << wid;
  221. }
  222.  
  223. UBigInt& UBigInt::operator >>=(const size_t& wid) {
  224. 	return *this = *this >> wid;
  225. }
  226.  
  227. UBigInt& UBigInt::operator ++() {
  228. 	return *this += 1;
  229. }
  230.  
  231. UBigInt UBigInt::operator ++(int) {
  232. 	UBigInt res = *this;
  233. 	*this += 1;
  234. 	return res;
  235. }
  236.  
  237. UBigInt& UBigInt::operator --() {
  238. 	return *this -= 1;
  239. }
  240.  
  241. UBigInt UBigInt::operator --(int) {
  242. 	UBigInt res = *this;
  243. 	*this -= 1;
  244. 	return res;
  245. }
  246.  
  247. bool UBigInt::operator ==(const UBigInt& num) const {
  248. 	return *this->fld == *num.fld;
  249. }
  250.  
  251. bool UBigInt::operator <(const UBigInt& num) const {
  252. 	return *this->fld < *num.fld;
  253. }
  254.  
  255. bool UBigInt::operator >(const UBigInt& num) const {
  256. 	return *this->fld > *num.fld;
  257. }
  258.  
  259. bool UBigInt::operator !=(const UBigInt& num) const {
  260. 	return *this->fld != *num.fld;
  261. }
  262.  
  263. bool UBigInt::operator <=(const UBigInt& num) const {
  264. 	return *this->fld <= *num.fld;
  265. }
  266.  
  267. bool UBigInt::operator >=(const UBigInt& num) const {
  268. 	return *this->fld >= *num.fld;
  269. }
  270.  
  271. UBigInt UBigInt::power(const UBigInt& exp) {
  272. 	if (isZero()) return UBigInt(false);
  273. 	UBigInt res(true);
  274. 	UBigInt coef = *this;
  275. 	for (UBigInt exp2 = exp;;) {
  276. 		if (exp2.getLSBit()) {
  277. 			res *= coef;
  278. 		}
  279. 		exp2 >>= 1;
  280. 		if (exp2.isZero()) break;
  281. 		coef *= coef;
  282. 	}
  283. 	return res;
  284. }
  285.  
  286. UBigInt UBigInt::modPower(const UBigInt& exp, const UBigInt& nrm) {
  287. 	if (nrm.isZero()) throw string("法がゼロ。");
  288. 	if (isZero()) return UBigInt(false);
  289. 	UBigInt res(true);
  290. 	UBigInt coef = *this % nrm;
  291. 	for (UBigInt exp2 = exp;;) {
  292. 		if (exp2.getLSBit()) {
  293. 			res = (res * coef) % nrm;
  294. 		}
  295. 		exp2 >>= 1;
  296. 		if (exp2.isZero()) break;
  297. 		coef = (coef * coef) % nrm;
  298. 	}
  299. 	return res;
  300. }
  301.  
  302. bool UBigInt::isZero() const {
  303. 	return this->fld->isZero();
  304. }
  305.  
  306. bool UBigInt::getLSBit() const {
  307. 	return this->fld->getLSBit();
  308. }
  309.  
  310. unsigned int UBigInt::getLSInt() const {
  311. 	return this->fld->getLSInt();
  312. }
  313.  
  314. string UBigInt::toString(const unsigned int& base) const {
  315. 	string res = "";
  316. 	BFPtr wrk(new BitField(*this->fld));
  317. 	BFPtr base_fld(new BitField(base));
  318. 	while (!wrk->isZero()) {
  319. 		BFPtr rem;
  320. 		wrk = divide(wrk, base_fld, &rem);
  321. 		res += figureToChar(rem->getLSInt());
  322. 	}
  323. 	if (res.empty()) res += '0';
  324. 	reverse(res.begin(), res.end());
  325. 	size_t pos = 0;
  326. 	for (; pos < res.length() - 1; pos++) if (res[pos] != '0') break;
  327. 	return res.substr(pos, res.length() - pos);
  328. }
  329.  
  330. UBigInt::BFPtr UBigInt::add(const BFPtr& age, const BFPtr& ade) {
  331. 	BFPtr sum(new BitField);
  332. 	unsigned int age_pos = 0;
  333. 	unsigned int ade_pos = 0;
  334. 	bool carry = false;
  335. 	while (age_pos < age->getWidth() || ade_pos < ade->getWidth()) {
  336. 		int age_num = age_pos < age->getWidth() ? (age->getBit(age_pos) == true ? 1 : 0) : 0;
  337. 		int ade_num = ade_pos < ade->getWidth() ? (ade->getBit(ade_pos) == true ? 1 : 0) : 0;
  338. 		int sum_num = age_num + ade_num + (carry ? 1 : 0);
  339. 		carry = sum_num > 1;
  340. 		if (carry) sum_num -= 2;
  341. 		sum->pushMSBit(sum_num == 1);
  342. 		if (age_pos < age->getWidth()) age_pos++;
  343. 		if (ade_pos < ade->getWidth()) ade_pos++;
  344. 	}
  345. 	if (sum->isEmpty()) sum->pushMSBit(false);
  346. 	if (carry) sum->pushMSBit(true);
  347. 	return sum;
  348. }
  349.  
  350. UBigInt::BFPtr UBigInt::subtract(const BFPtr& min, const BFPtr& sub) {
  351. 	BFPtr dif(new BitField);
  352. 	unsigned int min_pos = 0;
  353. 	unsigned int sub_pos = 0;
  354. 	bool borrow = false;
  355. 	while (min_pos < min->getWidth() || sub_pos < sub->getWidth()) {
  356. 		int min_num = min_pos < min->getWidth() ? (min->getBit(min_pos) == true ? 1 : 0) : 0;
  357. 		int sub_num = sub_pos < sub->getWidth() ? (sub->getBit(sub_pos) == true ? 1 : 0) : 0;
  358. 		int dif_num = min_num - sub_num - (borrow ? 1 : 0);
  359. 		borrow = dif_num < 0;
  360. 		if (borrow) dif_num += 2;
  361. 		dif->pushMSBit(dif_num == 1);
  362. 		if (min_pos < min->getWidth()) min_pos++;
  363. 		if (sub_pos < sub->getWidth()) sub_pos++;
  364. 	}
  365. 	if (borrow) throw string("被減数が減数より小さい。");
  366. 	if (dif->isEmpty()) dif->pushMSBit(false);
  367. 	dif->trim();
  368. 	return dif;
  369. }
  370.  
  371. UBigInt::BFPtr UBigInt::multiply(const BFPtr& mca, const BFPtr& mer) {
  372. 	BFPtr pro(new BitField(0));
  373. 	BFPtr wrk(new BitField(*mca));
  374. 	unsigned int mer_pos = 0;
  375. 	for (unsigned int mer_pos = 0; mer_pos < mer->getWidth(); mer_pos++) {
  376. 		if (mer->getBit(mer_pos) == true) pro = add(pro, wrk);
  377. 		wrk->shift(1);
  378. 	}
  379. 	return pro;
  380. }
  381.  
  382. UBigInt::BFPtr UBigInt::divide(const BFPtr& dde, const BFPtr& dsr, BFPtr* rem) {
  383. 	if (dsr->isZero()) throw string("除数がゼロ。");
  384. 	BFPtr quo(new BitField);
  385. 	BFPtr wnd(new BitField);
  386. 	for (unsigned int dde_next_pos = dde->getWidth(); dde_next_pos > 0; dde_next_pos--) {
  387. 		unsigned int dde_pos = dde_next_pos - 1;
  388. 		wnd->pushLSBit(dde->getBit(dde_pos));
  389. 		if (*wnd >= *dsr) {
  390. 			quo->pushLSBit(true);
  391. 			wnd = subtract(wnd, dsr);
  392. 		}
  393. 		else quo->pushLSBit(false);
  394. 	}
  395. 	if (quo->isEmpty()) quo->pushMSBit(false);
  396. 	if (rem) {
  397. 		*rem = wnd;
  398. 		if ((*rem)->isEmpty()) (*rem)->pushMSBit(false);
  399. 	}
  400. 	return quo;
  401. }
  402.  
  403. unsigned int UBigInt::charToFigure(const char& ch) {
  404. 	unsigned int res;
  405. 	if (ch >= '0' && ch <= '9') res = ch - '0';
  406. 	else if (ch >= 'A' && ch <= 'Z') res = 10 + ch - 'A';
  407. 	else if (ch >= 'a' && ch <= 'z') res = 10 + ch - 'a';
  408. 	else throw string("文字が数ではない。");
  409. 	return res;
  410. }
  411.  
  412. char UBigInt::figureToChar(const unsigned int& fig) {
  413. 	char res;
  414. 	if (fig >= 0 && fig <= 9) res = '0' + fig;
  415. 	else if (fig >= 10 && fig <= 36) res = 'A' + (fig - 10);
  416. 	else throw string("値が範囲を逸脱している。");
  417. 	return res;
  418. }
  419.  
  420. BitField::BitField() : buf(nullptr), buf_sz(0), beg(0), wid(0) {}
  421.  
  422. BitField::BitField(const unsigned int& num) {
  423. 	this->buf_sz = sizeof(unsigned int);
  424. 	this->buf = (unsigned char*)malloc(this->buf_sz);
  425. 	*(unsigned int*)this->buf = num;
  426. 	this->beg = 0;
  427. 	this->wid = sizeof(unsigned int) << 3;
  428. 	trim();
  429. }
  430.  
  431. BitField::BitField(const BitField& fld) : buf(nullptr), buf_sz(0), beg(0), wid(0) {
  432. 	if (fld.wid != 0) {
  433. 		this->buf_sz = fld.buf_sz;
  434. 		this->buf = (unsigned char*)malloc(this->buf_sz);
  435. 		memcpy(this->buf, fld.buf, fld.buf_sz);
  436. 		this->beg = fld.beg;
  437. 		this->wid = fld.wid;
  438. 	}
  439. }
  440.  
  441. BitField::~BitField() {
  442. 	if (this->buf) free(this->buf);
  443. }
  444.  
  445. BitField& BitField::operator =(const BitField& fld) {
  446. 	this->wid = 0;
  447. 	if (fld.wid != 0) {
  448. 		this->buf_sz = fld.buf_sz;
  449. 		this->buf = (unsigned char*)malloc(this->buf_sz);
  450. 		memcpy(this->buf, fld.buf, fld.buf_sz);
  451. 		this->beg = fld.beg;
  452. 		this->wid = fld.wid;
  453. 	}
  454. 	return *this;
  455. }
  456.  
  457. bool BitField::operator ==(const BitField& fld) const {
  458. 	return compare(fld) == 0;
  459. }
  460.  
  461. bool BitField::operator <(const BitField& fld) const {
  462. 	return compare(fld) < 0;
  463. }
  464.  
  465. bool BitField::operator >(const BitField& fld) const {
  466. 	return compare(fld) > 0;
  467. }
  468.  
  469. bool BitField::operator !=(const BitField& fld) const {
  470. 	return compare(fld) != 0;
  471. }
  472.  
  473. bool BitField::operator <=(const BitField& fld) const {
  474. 	return compare(fld) <= 0;
  475. }
  476.  
  477. bool BitField::operator >=(const BitField& fld) const {
  478. 	return compare(fld) >= 0;
  479. }
  480.  
  481. unsigned int BitField::getWidth() const {
  482. 	return this->wid;
  483. }
  484.  
  485. bool BitField::isEmpty() const {
  486. 	return this->wid == 0;
  487. }
  488.  
  489. bool BitField::isZero() const {
  490. 	bool res = true;
  491. 	for (unsigned int pos = 0; pos < this->wid; pos++) {
  492. 		if (getBit(pos) == true) {
  493. 			res = false;
  494. 			break;
  495. 		}
  496. 	}
  497. 	return res;
  498. }
  499.  
  500. bool BitField::getBit(const unsigned int& pos) const {
  501. 	unsigned int abs_pos = this->beg + pos;
  502. 	unsigned int buf_wid = this->buf_sz << 3;
  503. 	if (abs_pos >= buf_wid) abs_pos -= buf_wid;
  504. 	return ((this->buf[abs_pos >> 3] >> (abs_pos & 0x7)) & 1) == 1;
  505. }
  506.  
  507. bool BitField::getLSBit() const {
  508. 	return getBit(0);
  509. }
  510.  
  511. bool BitField::getMSBit() const {
  512. 	return getBit(this->wid - 1);
  513. }
  514.  
  515. unsigned int BitField::getLSInt() const {
  516. 	unsigned int res = 0;
  517. 	unsigned int int_wid = sizeof(unsigned int) << 3;
  518. 	for (unsigned int pos = 0; pos < int_wid && pos < this->wid; pos++) 
  519. 		res |= (getBit(pos) == true ? 1 : 0) << pos;
  520. 	return res;
  521. }
  522.  
  523. void BitField::setBit(const unsigned int& pos, const bool& bit) {
  524. 	unsigned int abs_pos = this->beg + pos;
  525. 	unsigned int buf_wid = this->buf_sz << 3;
  526. 	if (abs_pos >= buf_wid) abs_pos -= buf_wid;
  527. 	if (bit) this->buf[abs_pos >> 3] |= 1 << (abs_pos & 0x7);
  528. 	else this->buf[abs_pos >> 3] &= ~(1 << (abs_pos & 0x7));
  529. }
  530.  
  531. void BitField::pushMSBit(const bool& bit) {
  532. 	extendIfNecessary(1);
  533. 	setBit(this->wid - 1, bit);
  534. }
  535.  
  536. void BitField::pushLSBit(const bool& bit) {
  537. 	extendIfNecessary(-1);
  538. 	setBit(0, bit);
  539. }
  540.  
  541. void BitField::shift(const int& wid) {
  542. 	if (wid < 0) {
  543. 		this->beg -= wid;
  544. 		unsigned int buf_wid = this->buf_sz << 3;
  545. 		if (this->beg >= buf_wid) this->beg -= buf_wid;
  546. 		this->wid += wid;
  547. 	}
  548. 	else {
  549. 		extendIfNecessary(-wid);
  550. 		for (unsigned int pos = 0; pos < wid; pos++) 
  551. 			setBit(pos, false);
  552. 	}
  553. }
  554.  
  555. void BitField::trim() {
  556. 	while (this->wid != 0 && getMSBit() == false) this->wid--;
  557. }
  558.  
  559. void BitField::clear() {
  560. 	this->wid = 0;
  561. }
  562.  
  563. string BitField::toString() const {
  564. 	string res = "";
  565. 	for (unsigned int pos = 0; pos < this->wid; pos++) 
  566. 		res += getBit(pos) == true ? '1' : '0';
  567. 	return res;
  568. }
  569.  
  570. int BitField::compare(const BitField& fld) const {
  571. 	int res = 0;
  572. 	for (unsigned int next_pos = this->wid < fld.wid ? fld.wid : this->wid; next_pos > 0; next_pos--) {
  573. 		unsigned int pos = next_pos - 1;
  574. 		bool bit1 = pos < this->wid ? getBit(pos) : false;
  575. 		bool bit2 = pos < fld.wid ? fld.getBit(pos) : false;
  576. 		if (bit1 == false && bit2 == true) {
  577. 			res = -1;
  578. 			break;
  579. 		}
  580. 		else if (bit1 == true && bit2 == false) {
  581. 			res = 1;
  582. 			break;
  583. 		}
  584. 	}
  585. 	return res;
  586. }
  587.  
  588. void BitField::extendIfNecessary(const int& wid) {
  589. 	unsigned int abs_wid = wid < 0 ? -wid : wid;
  590. 	unsigned int need_sz = (this->wid + abs_wid + 7) >> 3;
  591. 	if (need_sz > this->buf_sz) {
  592. 		unsigned int new_buf_sz = need_sz << 1;
  593. 		unsigned char* new_buf = (unsigned char*)malloc(new_buf_sz);
  594. 		unsigned int new_beg = 0;
  595. 		if (this->wid != 0) {
  596. 			unsigned int fld_beg = this->beg >> 3;
  597. 			unsigned int fld_end = (this->beg + this->wid + 7) >> 3;
  598. 			if (fld_end <= this->buf_sz) {
  599. 				unsigned int fld_sz = fld_end - fld_beg;
  600. 				memcpy(new_buf + fld_beg, this->buf + fld_beg, fld_sz);
  601. 				new_beg = this->beg;
  602. 			}
  603. 			else {
  604. 				unsigned int low_sz = this->buf_sz - fld_beg;
  605. 				unsigned int new_low_beg = new_buf_sz - low_sz;
  606. 				memcpy(new_buf + new_low_beg, this->buf + fld_beg, low_sz);
  607. 				unsigned int high_sz = fld_end - this->buf_sz;
  608. 				memcpy(new_buf, this->buf, high_sz);
  609. 				unsigned int buf_wid = this->buf_sz << 3;
  610. 				unsigned int low_wid = buf_wid - this->beg;
  611. 				unsigned int new_buf_wid = new_buf_sz << 3;
  612. 				new_beg = new_buf_wid - low_wid;
  613. 			}
  614. 			free(this->buf);
  615. 		}
  616. 		this->buf_sz = new_buf_sz;
  617. 		this->buf = new_buf;
  618. 		this->beg = new_beg;
  619. 	}
  620. 	if (wid < 0) {
  621. 		this->beg += wid;
  622. 		int buf_wid = this->buf_sz << 3;
  623. 		if (this->beg < 0) this->beg += buf_wid;
  624. 	}
  625. 	this->wid += abs_wid;
  626. }
  627.  
  628. void assert(const char* pred_str, const bool& pred) {
  629. 	if (pred) {
  630. 		cout << "アサート成功: " << pred_str << endl;
  631. 	}
  632. 	else {
  633. 		cerr << "アサート失敗: " << pred_str << endl;
  634. 		exit(1);
  635. 	}
  636. }
  637.  
  638. int main() {
  639. 	try {
  640. 		clock_t begin = clock();
  641.  
  642. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("0")) == false)
  643. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("1")) == false)
  644. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("2")) == true)
  645. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("3")) == true)
  646. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("4")) == false)
  647. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("5")) == true)
  648. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("6")) == false)
  649. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("7")) == true)
  650. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("8")) == false)
  651. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("9")) == false)
  652. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("87")) == false)
  653. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("89")) == true)
  654. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("329")) == false)
  655. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("331")) == true)
  656. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("561")) == false)
  657. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("563")) == true)
  658. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("807")) == false)
  659. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("809")) == true)
  660. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("2251")) == true)
  661. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("59561")) == true)
  662. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("181243")) == true)
  663. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("14414443")) == true)
  664. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("10461401779")) == true)
  665. 		ASSERT(primalityTestMillerRabin(UBigInt::fromString("1853028778786433")) == true)
  666.  
  667. 		clock_t end = clock();
  668. 		clock_t elapsed = end - begin;
  669. 		cout << (elapsed / CLOCKS_PER_SEC) << "." << setfill('0') << setw(3) << ((elapsed % CLOCKS_PER_SEC) * 1000 / CLOCKS_PER_SEC) << " secs" << endl;
  670. 	}
  671. 	catch (const string& msg) {
  672. 		cerr << msg << endl;
  673. 		return 1;
  674. 	}
  675. 	return 0;
  676. }
  677.  
Success #stdin #stdout 1.56s 3064KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
アサート成功: primalityTestMillerRabin(UBigInt::fromString("0")) == false
アサート成功: primalityTestMillerRabin(UBigInt::fromString("1")) == false
アサート成功: primalityTestMillerRabin(UBigInt::fromString("2")) == true
アサート成功: primalityTestMillerRabin(UBigInt::fromString("3")) == true
アサート成功: primalityTestMillerRabin(UBigInt::fromString("4")) == false
アサート成功: primalityTestMillerRabin(UBigInt::fromString("5")) == true
アサート成功: primalityTestMillerRabin(UBigInt::fromString("6")) == false
アサート成功: primalityTestMillerRabin(UBigInt::fromString("7")) == true
アサート成功: primalityTestMillerRabin(UBigInt::fromString("8")) == false
アサート成功: primalityTestMillerRabin(UBigInt::fromString("9")) == false
アサート成功: primalityTestMillerRabin(UBigInt::fromString("87")) == false
アサート成功: primalityTestMillerRabin(UBigInt::fromString("89")) == true
アサート成功: primalityTestMillerRabin(UBigInt::fromString("329")) == false
アサート成功: primalityTestMillerRabin(UBigInt::fromString("331")) == true
アサート成功: primalityTestMillerRabin(UBigInt::fromString("561")) == false
アサート成功: primalityTestMillerRabin(UBigInt::fromString("563")) == true
アサート成功: primalityTestMillerRabin(UBigInt::fromString("807")) == false
アサート成功: primalityTestMillerRabin(UBigInt::fromString("809")) == true
アサート成功: primalityTestMillerRabin(UBigInt::fromString("2251")) == true
アサート成功: primalityTestMillerRabin(UBigInt::fromString("59561")) == true
アサート成功: primalityTestMillerRabin(UBigInt::fromString("181243")) == true
アサート成功: primalityTestMillerRabin(UBigInt::fromString("14414443")) == true
アサート成功: primalityTestMillerRabin(UBigInt::fromString("10461401779")) == true
アサート成功: primalityTestMillerRabin(UBigInt::fromString("1853028778786433")) == true
1.560 secs
https://ideone.com/7XJtSz
language:
C++14 (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!