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. #include <utility>
  10.  
  11. using namespace std;
  12.  
  13. class BigInt;
  14. class BitField;
  15.  
  16. template <class X> 
  17. class Pool {
  18. public:
  19.     class Ptr {
  20. 	public:
  21. 		Ptr();
  22. 		Ptr(const Ptr& ptr);
  23. 		virtual ~Ptr();
  24. 		Ptr& operator =(const Ptr& ptr);
  25. 		X& operator *() const;
  26. 		X* operator ->() const;
  27. 		X* get() const;
  28. 	protected:
  29. 		X* x;
  30. 		unsigned int* cnt;
  31. 		void release();
  32. 	};
  33. protected:
  34. 	struct Entry {
  35. 		X* x;
  36. 		unsigned int* cnt;
  37. 	};
  38. 	Entry* buf;
  39. 	unsigned int buf_sz;
  40. 	unsigned int cnt;
  41. 	Pool();
  42. 	virtual ~Pool();
  43. 	Entry get();
  44. 	void putBack(const Entry& ent);
  45. 	static Pool instance;
  46. 	friend Ptr;
  47. };
  48.  
  49. extern bool primalityTestMillerRabin(const BigInt& p, const unsigned int& cnt = 100);
  50.  
  51. class BigInt {
  52. public:
  53. 	BigInt(const int& num = 0);
  54. 	BigInt(const string& str, const unsigned int& base = 10);
  55. 	BigInt(const BigInt& num);
  56. 	BigInt operator -() const;
  57. 	BigInt operator +(const BigInt& ade) const;
  58. 	BigInt operator -(const BigInt& sub) const;
  59. 	BigInt operator *(const BigInt& mer) const;
  60. 	BigInt operator /(const BigInt& dsr) const;
  61. 	BigInt operator %(const BigInt& nrm) const;
  62. 	BigInt operator <<(const size_t& wid) const;
  63. 	BigInt operator >>(const size_t& wid) const;
  64. 	BigInt& operator =(const BigInt& num);
  65. 	BigInt& operator +=(const BigInt& ade);
  66. 	BigInt& operator -=(const BigInt& sub);
  67. 	BigInt& operator *=(const BigInt& mer);
  68. 	BigInt& operator /=(const BigInt& dsr);
  69. 	BigInt& operator %=(const BigInt& nrm);
  70. 	BigInt& operator <<=(const unsigned int& wid);
  71. 	BigInt& operator >>=(const unsigned int& wid);
  72. 	BigInt& operator ++();
  73. 	BigInt operator ++(int);
  74. 	BigInt& operator --();
  75. 	BigInt operator --(int);
  76. 	bool operator ==(const BigInt& num) const;
  77. 	bool operator <(const BigInt& num) const;
  78. 	bool operator >(const BigInt& num) const;
  79. 	bool operator !=(const BigInt& num) const;
  80. 	bool operator <=(const BigInt& num) const;
  81. 	bool operator >=(const BigInt& num) const;
  82. 	BigInt power(const BigInt& exp) const;
  83. 	BigInt modPower(const BigInt& exp, const BigInt& nrm) const;
  84. 	BigInt gcd(const BigInt& num) const;
  85. 	BigInt lcm(const BigInt& num) const;
  86. 	BigInt modInverse(const BigInt& num) const;
  87. 	bool isZero() const;
  88. 	int getSign() const;
  89. 	bool getLSBit() const;
  90. 	unsigned int getLSInt() const;
  91. 	string toString(const unsigned int& base = 10) const;
  92. protected:
  93. 	class BFPtr : public Pool<BitField>::Ptr {
  94. 	public:
  95. 		BFPtr();
  96. 		BFPtr(const unsigned int& num);
  97. 		BFPtr(const BitField& fld);
  98. 	};
  99. 	int sign;
  100. 	BFPtr fld;
  101. 	BigInt(const int& sign, const BFPtr& fld);
  102. 	static unsigned int INT_WID;
  103. 	static BFPtr add(const BFPtr& age, const BFPtr& ade);
  104. 	static BFPtr subtract(const BFPtr& min, const BFPtr& sub);
  105. 	static BFPtr multiply(const BFPtr& mca, const BFPtr& mer);
  106. 	static pair<BFPtr, BFPtr> divide(const BFPtr& dde, const BFPtr& dsr);
  107. 	static unsigned int charToFigure(const char& ch);
  108. 	static char figureToChar(const unsigned int& fig);
  109. };
  110.  
  111. class BitField {
  112. public:
  113. 	class IntInputStream {
  114. 	public:
  115. 		IntInputStream(const BitField* fld);
  116. 		bool isEOF() const;
  117. 		unsigned int getInt();
  118. 	protected:
  119. 		const BitField* fld;
  120. 		unsigned int end;
  121. 		unsigned int cur;
  122. 		unsigned int last;
  123. 		unsigned int low_wid;
  124. 		unsigned int high_wid;
  125. 		unsigned int low_mask;
  126. 		unsigned int high_mask;
  127. 		unsigned int rem;
  128. 		unsigned int num;
  129. 	};
  130. 	class IntOutputStream {
  131. 	public:
  132. 		IntOutputStream(BitField* fld);
  133. 		virtual ~IntOutputStream();
  134. 		void putInt(const unsigned int& num);
  135. 		void flush();
  136. 	protected:
  137. 		BitField* fld;
  138. 		unsigned int end;
  139. 		unsigned int cur;
  140. 		unsigned int low_wid;
  141. 		unsigned int high_wid;
  142. 		unsigned int low_mask;
  143. 		unsigned int high_mask;
  144. 		unsigned int high;
  145. 	};
  146. 	BitField();
  147. 	BitField(const unsigned int& num);
  148. 	BitField(const BitField& fld);
  149. 	virtual ~BitField();
  150. 	BitField& operator =(const BitField& fld);
  151. 	unsigned int getWidth() const;
  152. 	bool isEmpty() const;
  153. 	bool isZero() const;
  154. 	bool getBit(const unsigned int& pos) const;
  155. 	bool getLSBit() const;
  156. 	bool getMSBit() const;
  157. 	unsigned int getLSInt() const;
  158. 	void setBit(const unsigned int& pos, const bool& bit);
  159. 	void pushMSBit(const bool& bit);
  160. 	void pushLSBit(const bool& bit);
  161. 	void setInt(const unsigned int& num);
  162. 	void shift(const int& wid);
  163. 	void trim();
  164. 	void clear();
  165. 	int compare(const BitField& fld) const;
  166. 	string toString() const;
  167. protected:
  168. 	unsigned char* buf;
  169. 	unsigned int buf_sz;
  170. 	int beg;
  171. 	unsigned int wid;
  172. 	bool extendIfNecessary(const int& wid);
  173. 	friend IntInputStream;
  174. 	friend IntOutputStream;
  175. };
  176.  
  177. template <class X> 
  178. Pool<X>::Ptr::Ptr() {
  179. 	Entry ent = Pool<X>::instance.get();
  180. 	this->x = ent.x;
  181. 	this->cnt = ent.cnt;
  182. 	if (this->cnt) (*this->cnt)++;
  183. }
  184.  
  185. template <class X> 
  186. Pool<X>::Ptr::Ptr(const Ptr& ptr) : x(ptr.x), cnt(ptr.cnt) {
  187. 	if (this->cnt) (*this->cnt)++;
  188. }
  189.  
  190. template <class X> 
  191. Pool<X>::Ptr::~Ptr() {
  192. 	release();
  193. }
  194.  
  195. template <class X> 
  196. typename Pool<X>::Ptr& Pool<X>::Ptr::operator =(const Ptr& ptr) {
  197. 	release();
  198. 	this->x = ptr.x;
  199. 	this->cnt = ptr.cnt;
  200. 	if (this->cnt) (*this->cnt)++;
  201. 	return *this;
  202. }
  203.  
  204. template <class X> 
  205. X& Pool<X>::Ptr::operator *() const {
  206. 	return *this->x;
  207. }
  208.  
  209. template <class X> 
  210. X* Pool<X>::Ptr::operator ->() const {
  211. 	return this->x;
  212. }
  213.  
  214. template <class X> 
  215. X* Pool<X>::Ptr::get() const {
  216. 	return this->x;
  217. }
  218.  
  219. template <class X> 
  220. void Pool<X>::Ptr::release() {
  221. 	if (this->cnt && --*this->cnt == 0) {
  222. 		Entry ent;
  223. 		ent.x = this->x;
  224. 		ent.cnt = this->cnt;
  225. 		Pool<X>::instance.putBack(ent);
  226. 	}
  227. }
  228.  
  229. template <class X> 
  230. Pool<X>::Pool() : buf(nullptr), buf_sz(0), cnt(0) {}
  231.  
  232. template <class X> 
  233. Pool<X>::~Pool() {
  234. 	for (int i = 0; i < this->cnt; i++) {
  235. 		delete this->buf[i].x;
  236. 		free(this->buf[i].cnt);
  237. 	}
  238. 	free(this->buf);
  239. }
  240.  
  241. template <class X> 
  242. typename Pool<X>::Entry Pool<X>::get() {
  243. 	if (this->cnt == 0) {
  244. 		Entry ent;
  245. 		ent.x = new X;
  246. 		ent.cnt = new unsigned int(0);
  247. 		putBack(ent);
  248. 	}
  249. 	return this->buf[--this->cnt];
  250. }
  251.  
  252. template <class X> 
  253. void Pool<X>::putBack(const Entry& ent) {
  254. 	unsigned int need_sz = this->cnt + 1;
  255. 	if (need_sz > this->buf_sz) {
  256. 		unsigned int new_buf_sz = need_sz * 2;
  257. 		Entry* new_buf = (Entry*)malloc(sizeof(Entry) * new_buf_sz);
  258. 		if (this->buf_sz != 0) {
  259. 			memcpy(new_buf, this->buf, sizeof(Entry) * this->cnt);
  260. 			free(this->buf);
  261. 		}
  262. 		this->buf = new_buf;
  263. 		this->buf_sz = new_buf_sz;
  264. 	}
  265. 	this->buf[this->cnt++] = ent;
  266. }
  267.  
  268. template <class X> 
  269. Pool<X> Pool<X>::instance;
  270.  
  271. #define ASSERT(pred) assert(#pred, pred);
  272.  
  273. extern void assert(const char* pred_str, const bool& pred);
  274.  
  275. bool primalityTestMillerRabin(const BigInt& p, const unsigned int& cnt) {
  276. 	bool res = true;
  277. 	if (p == 1) res = false;
  278. 	else if (p == 2) res = true;
  279. 	else if (p.getLSBit() == false) res = false;
  280. 	else {
  281. 		BigInt o = p - 1;
  282. 		BigInt q = o;
  283. 		BigInt k(1);
  284. 		while (q.getLSBit() == false) {
  285. 			q >>= 1;
  286. 			k++;
  287. 		}
  288. 		BigInt a(2);
  289. 		BigInt gap((o - 2) / cnt);
  290. 		if (gap.isZero()) gap = 1;
  291. 		for (; a < p; a += gap) {
  292. 			BigInt b = a.modPower(q, p);
  293. 			if (b != 1 && b != o) {
  294. 				BigInt i(1);
  295. 				for (; i < k; i++) {
  296. 					b = (b * b) % p;
  297. 					if (b == o) break;
  298. 				}
  299. 				if (i == k) {
  300. 					res = false;
  301. 					break;
  302. 				}
  303. 			}
  304. 		}
  305. 	}
  306. 	return res;
  307. }
  308.  
  309. BigInt::BFPtr::BFPtr() {
  310. 	this->x->clear();
  311. }
  312.  
  313. BigInt::BFPtr::BFPtr(const unsigned int& num) {
  314. 	this->x->setInt(num);
  315. }
  316.  
  317. BigInt::BFPtr::BFPtr(const BitField& fld) {
  318. 	*this->x = fld;
  319. }
  320.  
  321. BigInt::BigInt(const int& num) {
  322. 	this->sign = num >= 0 ? 1 : -1;
  323. 	this->fld->setInt(this->sign * num);
  324. }
  325.  
  326. BigInt::BigInt(const string& str, const unsigned int& base) {
  327. 	this->sign = 1;
  328. 	this->fld->setInt(0);
  329. 	BFPtr base_fld(base);
  330. 	string::const_iterator iter = str.begin();
  331. 	if (*iter == '-') {
  332. 		this->sign = -1;
  333. 		iter++;
  334. 	}
  335. 	for (; iter != str.end(); iter++) {
  336. 		if (iter != str.begin()) {
  337. 			this->fld = multiply(this->fld, base_fld);
  338. 		}
  339. 		unsigned int fig = charToFigure(*iter);
  340. 		if (fig >= base) throw string("値が範囲を逸脱している。");
  341. 		BFPtr ade(fig);
  342. 		this->fld = add(this->fld, ade);
  343. 	}
  344. }
  345.  
  346. BigInt::BigInt(const int& sign, const BFPtr& fld) : sign(sign), fld(fld) {}
  347.  
  348. BigInt::BigInt(const BigInt& num) : sign(num.sign) {
  349. 	*this->fld = *num.fld;
  350. }
  351.  
  352. BigInt BigInt::operator -() const {
  353. 	return BigInt(-this->sign, this->fld);
  354. }
  355.  
  356. BigInt BigInt::operator +(const BigInt& ade) const {
  357. 	if (this->sign == ade.sign) 
  358. 		return BigInt(this->sign, add(this->fld, ade.fld));
  359. 	else {
  360. 		int sign;
  361. 		BFPtr gre_fld, less_fld;
  362. 		if (this->fld->compare(*ade.fld) >= 0) {
  363. 			sign = this->sign;
  364. 			gre_fld = this->fld;
  365. 			less_fld = ade.fld;
  366. 		}
  367. 		else {
  368. 			sign = ade.sign;
  369. 			gre_fld = ade.fld;
  370. 			less_fld = this->fld;
  371. 		}
  372. 		return BigInt(sign, subtract(gre_fld, less_fld));
  373. 	}
  374. }
  375.  
  376. BigInt BigInt::operator -(const BigInt& sub) const {
  377. 	return operator +(-sub);
  378. }
  379.  
  380. BigInt BigInt::operator *(const BigInt& mer) const {
  381. 	return BigInt(this->sign * mer.sign, multiply(this->fld, mer.fld));
  382. }
  383.  
  384. BigInt BigInt::operator /(const BigInt& dsr) const {
  385. 	return BigInt(this->sign * dsr.sign, divide(this->fld, dsr.fld).first);
  386. }
  387.  
  388. BigInt BigInt::operator %(const BigInt& nrm) const {
  389. 	if (nrm < 1) throw string("法が1より小さい。");
  390. 	return BigInt(this->sign, divide(this->fld, nrm.fld).second);
  391. }
  392.  
  393. BigInt BigInt::operator <<(const unsigned int& wid) const {
  394. 	BFPtr fld(*this->fld);
  395. 	fld->shift(wid);
  396. 	return BigInt(this->sign, fld);
  397. }
  398.  
  399. BigInt BigInt::operator >>(const unsigned int& wid) const {
  400. 	BFPtr fld(*this->fld);
  401. 	fld->shift(-wid);
  402. 	return BigInt(this->sign, fld);
  403. }
  404.  
  405. BigInt& BigInt::operator =(const BigInt& num) {
  406. 	this->sign = num.sign;
  407. 	*this->fld = *num.fld;
  408. 	return *this;
  409. }
  410.  
  411. BigInt& BigInt::operator +=(const BigInt& add) {
  412. 	return *this = *this + add;
  413. }
  414.  
  415. BigInt& BigInt::operator -=(const BigInt& sub) {
  416. 	return *this = *this - sub;
  417. }
  418.  
  419. BigInt& BigInt::operator *=(const BigInt& mer) {
  420. 	return *this = *this * mer;
  421. }
  422.  
  423. BigInt& BigInt::operator /=(const BigInt& dsr) {
  424. 	return *this = *this / dsr;
  425. }
  426.  
  427. BigInt& BigInt::operator %=(const BigInt& nrm) {
  428. 	return *this = *this % nrm;
  429. }
  430.  
  431. BigInt& BigInt::operator <<=(const size_t& wid) {
  432. 	return *this = *this << wid;
  433. }
  434.  
  435. BigInt& BigInt::operator >>=(const size_t& wid) {
  436. 	return *this = *this >> wid;
  437. }
  438.  
  439. BigInt& BigInt::operator ++() {
  440. 	return *this += 1;
  441. }
  442.  
  443. BigInt BigInt::operator ++(int) {
  444. 	BigInt res = *this;
  445. 	*this += 1;
  446. 	return res;
  447. }
  448.  
  449. BigInt& BigInt::operator --() {
  450. 	return *this -= 1;
  451. }
  452.  
  453. BigInt BigInt::operator --(int) {
  454. 	BigInt res = *this;
  455. 	*this -= 1;
  456. 	return res;
  457. }
  458.  
  459. bool BigInt::operator ==(const BigInt& num) const {
  460. 	return this->sign == num.sign && this->fld->compare(*num.fld) == 0;
  461. }
  462.  
  463. bool BigInt::operator <(const BigInt& num) const {
  464. 	int cmp_res = this->fld->compare(*num.fld);
  465. 	return (this->sign >= 0 && num.sign >= 0 && cmp_res < 0) || 
  466. 		(this->sign < 0 && num.sign >= 0) || 
  467. 		(this->sign < 0 && num.sign < 0 && cmp_res > 0);
  468. }
  469.  
  470. bool BigInt::operator >(const BigInt& num) const {
  471. 	int cmp_res = this->fld->compare(*num.fld);
  472. 	return (this->sign >= 0 && num.sign >= 0 && cmp_res > 0) || 
  473. 		(this->sign >= 0 && num.sign < 0) || 
  474. 		(this->sign < 0 && num.sign < 0 && cmp_res < 0);
  475. }
  476.  
  477. bool BigInt::operator !=(const BigInt& num) const {
  478. 	return !operator ==(num);
  479. }
  480.  
  481. bool BigInt::operator <=(const BigInt& num) const {
  482. 	return !operator >(num);
  483. }
  484.  
  485. bool BigInt::operator >=(const BigInt& num) const {
  486. 	return !operator <(num);
  487. }
  488.  
  489. BigInt BigInt::power(const BigInt& exp) const {
  490. 	if (exp.getSign() < 0) throw string("指数が負。");
  491. 	if (isZero()) return BigInt(0);
  492. 	BigInt res(1);
  493. 	BigInt coef = *this;
  494. 	for (BigInt exp2 = exp;;) {
  495. 		if (exp2.getLSBit()) {
  496. 			res *= coef;
  497. 		}
  498. 		exp2 >>= 1;
  499. 		if (exp2.isZero()) break;
  500. 		coef *= coef;
  501. 	}
  502. 	return res;
  503. }
  504.  
  505. BigInt BigInt::modPower(const BigInt& exp, const BigInt& nrm) const {
  506. 	if (nrm < 1) throw string("法が1より小さい。");
  507. 	if (isZero()) return BigInt(0);
  508. 	BigInt res(1);
  509. 	BigInt coef = *this % nrm;
  510. 	for (BigInt exp2 = exp;;) {
  511. 		if (exp2.getLSBit()) {
  512. 			res = (res * coef) % nrm;
  513. 		}
  514. 		exp2 >>= 1;
  515. 		if (exp2.isZero()) break;
  516. 		coef = (coef * coef) % nrm;
  517. 	}
  518. 	return res;
  519. }
  520.  
  521. BigInt BigInt::gcd(const BigInt& num) const {
  522. 	BigInt a(*this), b(num), r;
  523. 	if (a < b) swap(a, b);
  524. 	for (;;) {
  525. 		r = a % b;
  526. 		if (r == 0) break;
  527. 		a = b;
  528. 		b = r;
  529. 	};
  530. 	return b;
  531. }
  532.  
  533. BigInt BigInt::lcm(const BigInt& num) const {
  534. 	return *this * num / gcd(num);
  535. }
  536.  
  537. BigInt BigInt::modInverse(const BigInt& nrm) const {
  538. 	if (nrm < 1) throw string("法が1より小さい。");
  539. 	BigInt a(*this), b(nrm), r, q, c, d(1), e(0);
  540. 	if (a < b) {
  541. 		swap(a, b);
  542. 		swap(d, e);
  543. 	}
  544. 	for (;;) {
  545. 		q = a / b;
  546. 		r = a % b;
  547. 		if (r == 0) break;
  548. 		c = d - e * q;
  549. 		d = e;
  550. 		e = c;
  551. 		a = b;
  552. 		b = r;
  553. 	};
  554. 	if (c < 0) c += nrm;
  555. 	return c;
  556. }
  557.  
  558. bool BigInt::isZero() const {
  559. 	return this->fld->isZero();
  560. }
  561.  
  562. int BigInt::getSign() const {
  563. 	return this->sign;
  564. }
  565.  
  566. bool BigInt::getLSBit() const {
  567. 	return this->fld->getLSBit();
  568. }
  569.  
  570. unsigned int BigInt::getLSInt() const {
  571. 	return this->fld->getLSInt();
  572. }
  573.  
  574. string BigInt::toString(const unsigned int& base) const {
  575. 	string res = "";
  576. 	pair<BFPtr, BFPtr> quo_rem(BFPtr(*this->fld), BFPtr());
  577. 	BFPtr base_fld;
  578. 	base_fld->setInt(base);
  579. 	while (!quo_rem.first->isZero()) {
  580. 		quo_rem = divide(quo_rem.first, base_fld);
  581. 		res += figureToChar(quo_rem.second->getLSInt());
  582. 	}
  583. 	if (res.empty()) res += '0';
  584. 	if (this->sign < 0) res += '-';
  585. 	reverse(res.begin(), res.end());
  586. 	size_t pos = 0;
  587. 	for (; pos < res.length() - 1; pos++) if (res[pos] != '0') break;
  588. 	return res.substr(pos, res.length() - pos);
  589. }
  590.  
  591. unsigned int BigInt::INT_WID = sizeof(unsigned int) << 3;
  592.  
  593. BigInt::BFPtr BigInt::add(const BFPtr& age, const BFPtr& ade) {
  594. 	BFPtr sum;
  595. 	BitField::IntOutputStream sum_out(sum.get());
  596. 	BitField::IntInputStream age_in(age.get());
  597. 	BitField::IntInputStream ade_in(ade.get());
  598. 	bool carry = false;
  599. 	while (!age_in.isEOF() || !ade_in.isEOF()) {
  600. 		unsigned int age_num = !age_in.isEOF() ? age_in.getInt() : 0;
  601. 		unsigned int ade_num = !ade_in.isEOF() ? ade_in.getInt() : 0;
  602. 		unsigned int sum_num = (age_num & ~(1 << (INT_WID - 1))) + (ade_num & ~(1 << (INT_WID - 1))) + (carry ? 1 : 0);
  603. 		int ms_num = (age_num >> (INT_WID - 1)) + (ade_num >> (INT_WID - 1)) + (sum_num >> (INT_WID - 1));
  604. 		carry = ms_num > 1;
  605. 		if (carry) ms_num -= 2;
  606. 		sum_num = (sum_num & ~(1 << (INT_WID - 1))) | (ms_num << (INT_WID - 1));
  607. 		sum_out.putInt(sum_num);
  608. 	}
  609. 	sum_out.flush();
  610. 	if (carry) sum->pushMSBit(true);
  611. 	if (sum->isEmpty()) sum->pushMSBit(false);
  612. 	sum->trim();
  613. 	return sum;
  614. }
  615.  
  616. BigInt::BFPtr BigInt::subtract(const BFPtr& min, const BFPtr& sub) {
  617. 	BFPtr dif;
  618. 	BitField::IntOutputStream dif_out(dif.get());
  619. 	BitField::IntInputStream min_in(min.get());
  620. 	BitField::IntInputStream sub_in(sub.get());
  621. 	bool borrow = false;
  622. 	while (!min_in.isEOF() || !sub_in.isEOF()) {
  623. 		unsigned int min_num = !min_in.isEOF() ? min_in.getInt() : 0;
  624. 		unsigned int sub_num = !sub_in.isEOF() ? sub_in.getInt() : 0;
  625. 		unsigned int dif_num = (min_num | (1 << (INT_WID - 1))) - (sub_num & ~(1 << (INT_WID - 1))) - (borrow ? 1 : 0);
  626. 		int ms_num = (min_num >> (INT_WID - 1)) - (sub_num >> (INT_WID - 1)) - (1 - (dif_num >> (INT_WID - 1)));
  627. 		borrow = ms_num < 0;
  628. 		if (borrow) ms_num += 2;
  629. 		dif_num = (dif_num & ~(1 << (INT_WID - 1))) | (ms_num << (INT_WID - 1));
  630. 		dif_out.putInt(dif_num);
  631. 	}
  632. 	dif_out.flush();
  633. 	if (borrow) throw string("被減数が減数より小さい。");
  634. 	if (dif->isEmpty()) dif->pushMSBit(false);
  635. 	dif->trim();
  636. 	return dif;
  637. }
  638.  
  639. BigInt::BFPtr BigInt::multiply(const BFPtr& mca, const BFPtr& mer) {
  640. 	BFPtr pro(0);
  641. 	BFPtr wrk(*mca);
  642. 	for (unsigned int mer_pos = 0; mer_pos < mer->getWidth(); mer_pos++) {
  643. 		if (mer->getBit(mer_pos) == true) pro = add(pro, wrk);
  644. 		wrk->shift(1);
  645. 	}
  646. 	return pro;
  647. }
  648.  
  649. pair<BigInt::BFPtr, BigInt::BFPtr> BigInt::divide(const BFPtr& dde, const BFPtr& dsr) {
  650. 	if (dsr->isZero()) throw string("除数がゼロ。");
  651. 	pair<BFPtr, BFPtr> quo_rem;
  652. 	for (unsigned int dde_next_pos = dde->getWidth(); dde_next_pos > 0; dde_next_pos--) {
  653. 		unsigned int dde_pos = dde_next_pos - 1;
  654. 		quo_rem.second->pushLSBit(dde->getBit(dde_pos));
  655. 		if (quo_rem.second->compare(*dsr) >= 0) {
  656. 			quo_rem.first->pushLSBit(true);
  657. 			quo_rem.second = subtract(quo_rem.second, dsr);
  658. 		}
  659. 		else quo_rem.first->pushLSBit(false);
  660. 	}
  661. 	if (quo_rem.first->isEmpty()) quo_rem.first->pushMSBit(false);
  662. 	if (quo_rem.second->isEmpty()) quo_rem.second->pushMSBit(false);
  663. 	return quo_rem;
  664. }
  665.  
  666. unsigned int BigInt::charToFigure(const char& ch) {
  667. 	unsigned int res;
  668. 	if (ch >= '0' && ch <= '9') res = ch - '0';
  669. 	else if (ch >= 'A' && ch <= 'Z') res = 10 + ch - 'A';
  670. 	else if (ch >= 'a' && ch <= 'z') res = 10 + ch - 'a';
  671. 	else throw string("文字が数ではない。");
  672. 	return res;
  673. }
  674.  
  675. char BigInt::figureToChar(const unsigned int& fig) {
  676. 	char res;
  677. 	if (fig >= 0 && fig <= 9) res = '0' + fig;
  678. 	else if (fig >= 10 && fig <= 36) res = 'A' + (fig - 10);
  679. 	else throw string("値が範囲を逸脱している。");
  680. 	return res;
  681. }
  682.  
  683. BitField::IntInputStream::IntInputStream(const BitField* fld) {
  684. 	this->fld = fld;
  685. 	this->end = fld->buf_sz / sizeof(unsigned int);
  686. 	this->cur = (this->fld->beg >> 3) / sizeof(unsigned int);
  687. 	unsigned int fld_end = this->fld->beg + this->fld->wid;
  688. 	unsigned int buf_wid = this->fld->buf_sz << 3;
  689. 	unsigned int act_fld_end;
  690. 	if (fld_end <= buf_wid) act_fld_end = fld_end;
  691. 	else act_fld_end = fld_end - buf_wid;
  692. 	this->last = ((act_fld_end - 1) >> 3) / sizeof(unsigned int);
  693. 	this->high_wid = this->fld->beg & ((sizeof(unsigned int) << 3) - 1);
  694. 	this->low_wid = (sizeof(unsigned int) << 3) - this->high_wid;
  695. 	this->high_mask = (1 << this->high_wid) - 1;
  696. 	this->low_mask = ~this->high_mask;
  697. 	this->rem = this->fld->wid;
  698. 	if (this->fld->wid != 0) this->num = ((unsigned int*)this->fld->buf)[this->cur];
  699. }
  700.  
  701. bool BitField::IntInputStream::isEOF() const {
  702. 	return this->rem == 0;
  703. }
  704.  
  705. unsigned int BitField::IntInputStream::getInt() {
  706. 	unsigned int res = 0;
  707. 	res |= (this->num & this->low_mask) >> this->high_wid;
  708. 	if (this->rem >= this->low_wid) {
  709. 		this->rem -= this->low_wid;
  710. 		if (this->rem != 0) {
  711. 			this->cur++;
  712. 			if (this->cur == this->end) this->cur = 0;
  713. 			this->num = ((unsigned int*)this->fld->buf)[this->cur];
  714. 			if (this->high_wid != 0) {
  715. 				res |= (this->num & this->high_mask) << this->low_wid;
  716. 				if (this->rem >= this->high_wid) 
  717. 					this->rem -= this->high_wid;
  718. 				else {
  719. 					res &= (1 << (this->low_wid + this->rem)) - 1;
  720. 					this->rem = 0;
  721. 				}
  722. 			}
  723. 		}
  724. 	}
  725. 	else {
  726. 		res &= (1 << this->rem) - 1;
  727. 		this->rem = 0;
  728. 	}
  729. 	return res;
  730. }
  731.  
  732. BitField::IntOutputStream::IntOutputStream(BitField* fld) {
  733. 	this->fld = fld;
  734. 	this->end = this->fld->buf_sz / sizeof(unsigned int);
  735. 	unsigned int fld_end = this->fld->beg + this->fld->wid;
  736. 	unsigned int buf_wid = this->fld->buf_sz << 3;
  737. 	unsigned int act_fld_end;
  738. 	if (fld_end <= buf_wid) act_fld_end = fld_end;
  739. 	else act_fld_end = fld_end - buf_wid;
  740. 	this->cur = (act_fld_end >> 3) / sizeof(unsigned int);
  741. 	this->high_wid = act_fld_end & ((sizeof(unsigned int) << 3) - 1);
  742. 	this->low_wid = (sizeof(unsigned int) << 3) - this->high_wid;
  743. 	this->high_mask = (1 << this->high_wid) - 1;
  744. 	this->low_mask = ~this->high_mask;
  745. 	if (this->fld->wid != 0) 
  746. 		this->high = ((unsigned int*)this->fld->buf)[this->cur] & this->high_mask;
  747. 	else this->high = 0;
  748. }
  749.  
  750. BitField::IntOutputStream::~IntOutputStream() {
  751. 	flush();
  752. }
  753.  
  754. void BitField::IntOutputStream::putInt(const unsigned int& num) {
  755. 	this->fld->extendIfNecessary(sizeof(unsigned int) << 3);
  756. 	((unsigned int*)this->fld->buf)[this->cur] = this->high | ((num << this->high_wid) & this->low_mask);
  757. 	this->cur++;
  758. 	if (this->high_wid != 0) 
  759. 		this->high = num >> this->low_wid;
  760. }
  761.  
  762. void BitField::IntOutputStream::flush() {
  763. 	if (this->high_wid != 0) 
  764. 		((unsigned int*)this->fld->buf)[this->cur] = this->high | (((unsigned int*)this->fld->buf)[this->cur] & this->low_mask);
  765. }
  766.  
  767. BitField::BitField() : buf(nullptr), buf_sz(0), beg(0), wid(0) {}
  768.  
  769. BitField::BitField(const unsigned int& num) : buf(nullptr), buf_sz(0), beg(0), wid(0) {
  770. 	extendIfNecessary(sizeof(unsigned int) << 3);
  771. 	*(unsigned int*)this->buf = num;
  772. 	trim();
  773. }
  774.  
  775. BitField::BitField(const BitField& fld) : buf(nullptr), buf_sz(0), beg(0), wid(0) {
  776. 	if (fld.wid != 0) {
  777. 		this->buf_sz = fld.buf_sz;
  778. 		this->buf = (unsigned char*)malloc(this->buf_sz);
  779. 		memcpy(this->buf, fld.buf, fld.buf_sz);
  780. 		this->beg = fld.beg;
  781. 		this->wid = fld.wid;
  782. 	}
  783. }
  784.  
  785. BitField::~BitField() {
  786. 	if (this->buf) free(this->buf);
  787. }
  788.  
  789. BitField& BitField::operator =(const BitField& fld) {
  790. 	this->wid = 0;
  791. 	if (fld.wid != 0) {
  792. 		this->buf_sz = fld.buf_sz;
  793. 		this->buf = (unsigned char*)malloc(this->buf_sz);
  794. 		memcpy(this->buf, fld.buf, fld.buf_sz);
  795. 		this->beg = fld.beg;
  796. 		this->wid = fld.wid;
  797. 	}
  798. 	return *this;
  799. }
  800.  
  801. unsigned int BitField::getWidth() const {
  802. 	return this->wid;
  803. }
  804.  
  805. bool BitField::isEmpty() const {
  806. 	return this->wid == 0;
  807. }
  808.  
  809. bool BitField::isZero() const {
  810. 	bool res = true;
  811. 	for (unsigned int pos = 0; pos < this->wid; pos++) {
  812. 		if (getBit(pos) == true) {
  813. 			res = false;
  814. 			break;
  815. 		}
  816. 	}
  817. 	return res;
  818. }
  819.  
  820. bool BitField::getBit(const unsigned int& pos) const {
  821. 	unsigned int abs_pos = this->beg + pos;
  822. 	unsigned int buf_wid = this->buf_sz << 3;
  823. 	if (abs_pos >= buf_wid) abs_pos -= buf_wid;
  824. 	return ((this->buf[abs_pos >> 3] >> (abs_pos & 0x7)) & 1) == 1;
  825. }
  826.  
  827. bool BitField::getLSBit() const {
  828. 	return getBit(0);
  829. }
  830.  
  831. bool BitField::getMSBit() const {
  832. 	return getBit(this->wid - 1);
  833. }
  834.  
  835. unsigned int BitField::getLSInt() const {
  836. 	unsigned int res = 0;
  837. 	unsigned int int_wid = sizeof(unsigned int) << 3;
  838. 	for (unsigned int pos = 0; pos < int_wid && pos < this->wid; pos++) 
  839. 		res |= (getBit(pos) == true ? 1 : 0) << pos;
  840. 	return res;
  841. }
  842.  
  843. void BitField::setBit(const unsigned int& pos, const bool& bit) {
  844. 	unsigned int abs_pos = this->beg + pos;
  845. 	unsigned int buf_wid = this->buf_sz << 3;
  846. 	if (abs_pos >= buf_wid) abs_pos -= buf_wid;
  847. 	if (bit) this->buf[abs_pos >> 3] |= 1 << (abs_pos & 0x7);
  848. 	else this->buf[abs_pos >> 3] &= ~(1 << (abs_pos & 0x7));
  849. }
  850.  
  851. void BitField::pushMSBit(const bool& bit) {
  852. 	extendIfNecessary(1);
  853. 	setBit(this->wid - 1, bit);
  854. }
  855.  
  856. void BitField::pushLSBit(const bool& bit) {
  857. 	extendIfNecessary(-1);
  858. 	setBit(0, bit);
  859. }
  860.  
  861. void BitField::setInt(const unsigned int& num) {
  862. 	clear();
  863. 	extendIfNecessary(sizeof(unsigned int) << 3);
  864. 	*(unsigned int*)this->buf = num;
  865. 	trim();
  866. }
  867.  
  868. void BitField::shift(const int& wid) {
  869. 	if (wid < 0) {
  870. 		this->beg -= wid;
  871. 		unsigned int buf_wid = this->buf_sz << 3;
  872. 		if (this->beg >= buf_wid) this->beg -= buf_wid;
  873. 		this->wid += wid;
  874. 	}
  875. 	else {
  876. 		extendIfNecessary(-wid);
  877. 		for (unsigned int pos = 0; pos < wid; pos++) 
  878. 			setBit(pos, false);
  879. 	}
  880. }
  881.  
  882. void BitField::trim() {
  883. 	while (this->wid != 0 && getMSBit() == false) this->wid--;
  884. }
  885.  
  886. void BitField::clear() {
  887. 	this->beg = 0;
  888. 	this->wid = 0;
  889. }
  890.  
  891. int BitField::compare(const BitField& fld) const {
  892. 	int res = 0;
  893. 	for (unsigned int next_pos = this->wid < fld.wid ? fld.wid : this->wid; next_pos > 0; next_pos--) {
  894. 		unsigned int pos = next_pos - 1;
  895. 		bool bit1 = pos < this->wid ? getBit(pos) : false;
  896. 		bool bit2 = pos < fld.wid ? fld.getBit(pos) : false;
  897. 		if (bit1 == false && bit2 == true) {
  898. 			res = -1;
  899. 			break;
  900. 		}
  901. 		else if (bit1 == true && bit2 == false) {
  902. 			res = 1;
  903. 			break;
  904. 		}
  905. 	}
  906. 	return res;
  907. }
  908.  
  909. string BitField::toString() const {
  910. 	string res = "";
  911. 	for (unsigned int pos = 0; pos < this->wid; pos++) 
  912. 		res += getBit(pos) == true ? '1' : '0';
  913. 	return res;
  914. }
  915.  
  916. bool BitField::extendIfNecessary(const int& wid) {
  917. 	bool res = false;
  918. 	unsigned int abs_wid = wid < 0 ? -wid : wid;
  919. 	unsigned int need_sz = (this->wid + abs_wid + 7) >> 3;
  920. 	if (need_sz > this->buf_sz) {
  921. 		unsigned int new_buf_sz = need_sz << 1;
  922. 		new_buf_sz = ((new_buf_sz + 3) >> 2) << 2;
  923. 		unsigned char* new_buf = (unsigned char*)malloc(new_buf_sz);
  924. 		unsigned int new_beg = 0;
  925. 		if (this->wid != 0) {
  926. 			unsigned int fld_beg = this->beg >> 3;
  927. 			unsigned int fld_end = (this->beg + this->wid + 7) >> 3;
  928. 			if (fld_end <= this->buf_sz) {
  929. 				unsigned int fld_sz = fld_end - fld_beg;
  930. 				memcpy(new_buf + fld_beg, this->buf + fld_beg, fld_sz);
  931. 				new_beg = this->beg;
  932. 			}
  933. 			else {
  934. 				unsigned int low_sz = this->buf_sz - fld_beg;
  935. 				unsigned int new_low_beg = new_buf_sz - low_sz;
  936. 				memcpy(new_buf + new_low_beg, this->buf + fld_beg, low_sz);
  937. 				unsigned int high_sz = fld_end - this->buf_sz;
  938. 				memcpy(new_buf, this->buf, high_sz);
  939. 				unsigned int buf_wid = this->buf_sz << 3;
  940. 				unsigned int low_wid = buf_wid - this->beg;
  941. 				unsigned int new_buf_wid = new_buf_sz << 3;
  942. 				new_beg = new_buf_wid - low_wid;
  943. 			}
  944. 			free(this->buf);
  945. 			res = true;
  946. 		}
  947. 		this->buf_sz = new_buf_sz;
  948. 		this->buf = new_buf;
  949. 		this->beg = new_beg;
  950. 	}
  951. 	if (wid < 0) {
  952. 		this->beg += wid;
  953. 		int buf_wid = this->buf_sz << 3;
  954. 		if (this->beg < 0) this->beg += buf_wid;
  955. 	}
  956. 	this->wid += abs_wid;
  957. 	return res;
  958. }
  959.  
  960. void assert(const char* pred_str, const bool& pred) {
  961. 	if (pred) {
  962. 		cout << "アサート成功: " << pred_str << endl;
  963. 	}
  964. 	else {
  965. 		cerr << "アサート失敗: " << pred_str << endl;
  966. 		exit(1);
  967. 	}
  968. }
  969.  
  970. int main() {
  971. 	try {
  972. 		clock_t begin = clock();
  973.  
  974. 		ASSERT(primalityTestMillerRabin(BigInt("10461401779")) == true)
  975.  
  976. 		clock_t end = clock();
  977. 		clock_t elapsed = end - begin;
  978. 		cout << (elapsed / CLOCKS_PER_SEC) << "." << setfill('0') << setw(3) << ((elapsed % CLOCKS_PER_SEC) * 1000 / CLOCKS_PER_SEC) << " secs" << endl;
  979. 	}
  980. 	catch (const string& msg) {
  981. 		cerr << msg << endl;
  982. 		return 1;
  983. 	}
  984. 	return 0;
  985. }
  986.  
Success #stdin #stdout 0.09s 3716KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
アサート成功: primalityTestMillerRabin(BigInt("10461401779")) == true
0.090 secs
https://ideone.com/ozEqPI
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!