API tools faq
paste
Advertisement
gmusya

Untitled

gmusya
Dec 18th, 2022
78
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 17.18 KB | None | 0 0
raw download clone embed print report
  1. #pragma GCC optimize("O3")
  2.  
  3. #include <algorithm>
  4. #include <ctime>
  5. #include <iostream>
  6. #include <random>
  7. #include <set>
  8. #include <utility>
  9. #include <vector>
  10.  
  11. #define int ll
  12.  
  13. using namespace std;
  14.  
  15. const bool DEBUG = false;
  16.  
  17. using ll = __int128;
  18. using uint128 = unsigned __int128;
  19.  
  20. int CNT = 0;
  21.  
  22. const int BASE = 1e18;
  23. const int x = 4294967296;
  24. const uint128 BASE2 = x * x;
  25.  
  26. struct Number10 {
  27. bool negative = false;
  28. vector<int> digits;
  29.  
  30. explicit Number10(int x) {
  31. if (x < BASE) {
  32. digits = {x};
  33. } else {
  34. while (x) {
  35. digits.push_back(x % BASE);
  36. x /= BASE;
  37. }
  38. }
  39. }
  40.  
  41. explicit Number10(string str) {
  42. reverse(str.begin(), str.end());
  43. int value = 0;
  44. int cnt = 0;
  45. int multiplier = 1;
  46. for (auto& now: str) {
  47. if (cnt == 18) {
  48. digits.push_back(value);
  49. value = 0;
  50. multiplier = 1;
  51. cnt = 0;
  52. }
  53. ++cnt;
  54. value += multiplier * int(now - '0');
  55. multiplier *= 10;
  56. }
  57. digits.push_back(value);
  58. }
  59.  
  60. explicit Number10(const vector<int>& value) {
  61. digits = value;
  62. }
  63.  
  64. Number10& operator=(const Number10& other) = default;
  65.  
  66. const int& operator[](size_t ind) const {
  67. return digits[ind];
  68. }
  69.  
  70. size_t size() const {
  71. return digits.size();
  72. }
  73.  
  74. Number10 shift(size_t cnt) const {
  75. vector<int> result(cnt);
  76. for (auto& now: digits) {
  77. result.push_back(now);
  78. }
  79. return Number10(result);
  80. }
  81.  
  82. Number10 operator+(const Number10& other) const {
  83. if (other.negative) {
  84. return *this - (-other);
  85. }
  86. if (negative) {
  87. return other - (-*this);
  88. }
  89. vector<int> result(max(size(), other.size()));
  90. for (size_t i = 0; i < size(); ++i) {
  91. result[i] += digits[i];
  92. }
  93. for (size_t i = 0; i < other.size(); ++i) {
  94. result[i] += other[i];
  95. }
  96. for (size_t i = 0; i < result.size(); ++i) {
  97. if (result[i] >= BASE) {
  98. if (i + 1 == result.size()) {
  99. result.push_back(0);
  100. }
  101. result[i + 1] += result[i] / BASE;
  102. result[i] %= BASE;
  103. }
  104. }
  105. return Number10(result);
  106. }
  107.  
  108. Number10 operator-() const {
  109. Number10 x(digits);
  110. x.negative = !negative;
  111. return x;
  112. }
  113.  
  114. Number10 operator-(const Number10& other) const {
  115. if (other.negative) {
  116. return *this + (-other);
  117. }
  118. if (negative) {
  119. return -(other + (-*this));
  120. }
  121. if (*this >= other) {
  122. vector<int> result = digits;
  123. for (size_t i = 0; i < other.size(); ++i) {
  124. result[i] -= other[i];
  125. }
  126. for (size_t i = 0; i + 1 < result.size(); ++i) {
  127. if (result[i] < 0) {
  128. result[i] += BASE;
  129. result[i + 1] -= 1;
  130. }
  131. }
  132. while (result.size() > 1 && result.back() == 0) {
  133. result.pop_back();
  134. }
  135. return Number10(result);
  136. } else {
  137. Number10 result(other - *this);
  138. result.negative = true;
  139. return result;
  140. }
  141. }
  142.  
  143. Number10& operator+=(const Number10& other) {
  144. return *this = *this + other;
  145. }
  146.  
  147. Number10& operator-=(const Number10& other) {
  148. return *this = *this - other;
  149. }
  150.  
  151. Number10 operator*(int value) const {
  152. vector<int> result(size());
  153. for (size_t i = 0; i < result.size(); ++i) {
  154. if (i < digits.size()) {
  155. result[i] += digits[i] * value;
  156. }
  157. if (result[i] >= BASE && i + 1 == result.size()) {
  158. result.push_back(0);
  159. }
  160. if (result[i] >= BASE) {
  161. result[i + 1] += result[i] / BASE;
  162. result[i] %= BASE;
  163. }
  164. }
  165. return Number10(result);
  166. }
  167.  
  168. Number10 operator*(const Number10& other) const {
  169. Number10 result(string("0"));
  170. for (size_t i = 0; i < size(); ++i) {
  171. result += (other * digits[i]).shift(i);
  172. }
  173. result.negative = negative;
  174. if (other.negative) {
  175. result.negative = !result.negative;
  176. }
  177. return result;
  178. }
  179.  
  180. Number10 operator*=(const Number10& other) {
  181. return *this = *this * other;
  182. }
  183.  
  184. Number10 operator/(const Number10& other) const {
  185. Number10 number = *this;
  186. size_t cnt = number.size();
  187. vector<int> result(cnt);
  188. for (size_t i = cnt; i >= 1; --i) {
  189. auto it2 = other.shift(i - 1);
  190. int rhs = other.digits.back();
  191. int lhs = 0;
  192. if (other.size() + (i - 2) < number.size()) {
  193. lhs += number[other.size() + (i - 2)];
  194. }
  195. if (other.size() + (i - 1) < number.size()) {
  196. lhs += BASE * number[other.size() + (i - 1)];
  197. }
  198. int x = (lhs + 1) / rhs;
  199. for (; x >= 1;) {
  200. auto it = it2 * x;
  201. if (number >= it) {
  202. number -= it;
  203. result[i - 1] += x;
  204. }
  205. if (x == 1) {
  206. break;
  207. }
  208. int rhs = other.digits.back();
  209. int lhs = 0;
  210. if (other.size() + (i - 2) < number.size()) {
  211. lhs += number[other.size() + (i - 2)];
  212. }
  213. if (other.size() + (i - 1) < number.size()) {
  214. lhs += BASE * number[other.size() + (i - 1)];
  215. }
  216. x = min((x + 1) / 2, (lhs + 1) / rhs);
  217. }
  218. }
  219. while (result.size() > 1 && result.back() == 0) {
  220. result.pop_back();
  221. }
  222. return Number10(result);
  223. }
  224.  
  225. Number10 operator%(const Number10& other) const {
  226. Number10 number = *this;
  227. size_t cnt = number.size();
  228. vector<int> result(cnt);
  229. for (size_t i = cnt; i >= 1; --i) {
  230. auto it2 = other.shift(i - 1);
  231. int rhs = other.digits.back();
  232. int lhs = 0;
  233. if (other.size() + (i - 2) < number.size()) {
  234. lhs += number[other.size() + (i - 2)];
  235. }
  236. if (other.size() + (i - 1) < number.size()) {
  237. lhs += BASE * number[other.size() + (i - 1)];
  238. }
  239. int x = (lhs + 1) / rhs;
  240. for (; x >= 1;) {
  241. auto it = it2 * x;
  242. if (number >= it) {
  243. number -= it;
  244. result[i - 1] += x;
  245. }
  246. if (x == 1) {
  247. break;
  248. }
  249. int rhs = other.digits.back();
  250. int lhs = 0;
  251. if (other.size() + (i - 2) < number.size()) {
  252. lhs += number[other.size() + (i - 2)];
  253. }
  254. if (other.size() + (i - 1) < number.size()) {
  255. lhs += BASE * number[other.size() + (i - 1)];
  256. }
  257. x = min((x + 1) / 2, (lhs + 1) / rhs);
  258. }
  259. }
  260. while (result.size() > 1 && result.back() == 0) {
  261. result.pop_back();
  262. }
  263. return number;
  264. }
  265.  
  266. int operator%(int val) const {
  267. Number10 result = *this;
  268. int carry = 0;
  269. for (size_t i = result.size(); i >= 1; --i) {
  270. int cur = result[i - 1] + carry * 1ll * BASE;
  271. result.digits[i - 1] = int(cur / val);
  272. carry = int(cur % val);
  273. }
  274. return carry;
  275. }
  276.  
  277. Number10 operator/(int val) const {
  278. Number10 result = *this;
  279. int carry = 0;
  280. for (size_t i = result.size(); i >= 1; --i) {
  281. int cur = result[i - 1] + carry * 1ll * BASE;
  282. result.digits[i - 1] = int(cur / val);
  283. carry = int(cur % val);
  284. }
  285. while (result.digits.size() > 1 && result.digits.back() == 0) {
  286. result.digits.pop_back();
  287. }
  288. return result;
  289. }
  290.  
  291. bool operator<(const Number10& other) const {
  292. if (size() != other.size()) {
  293. return size() < other.size();
  294. }
  295. for (size_t i = size(); i >= 1; --i) {
  296. if (digits[i - 1] != other[i - 1]) {
  297. return digits[i - 1] < other[i - 1];
  298. }
  299. }
  300. return false;
  301. }
  302.  
  303. bool operator>(const Number10& other) const {
  304. return (other < *this);
  305. }
  306.  
  307. bool operator<=(const Number10& other) const {
  308. return !(*this > other);
  309. }
  310.  
  311. bool operator>=(const Number10& other) const {
  312. return !(*this < other);
  313. }
  314.  
  315. bool operator==(const Number10& other) const {
  316. return digits == other.digits;
  317. }
  318.  
  319. bool operator!=(const Number10& other) const {
  320. return !(*this == other);
  321. }
  322.  
  323. friend ostream& operator<<(ostream& out, const Number10& number) {
  324. bool good = false;
  325. if (number == Number10(0)) {
  326. return out << "0";
  327. }
  328. if (number.negative) {
  329. out << "-";
  330. }
  331. for (size_t i = number.size(); i >= 1; --i) {
  332. auto it = BASE / 10;
  333. while (it) {
  334. if (good || int32_t(number[i - 1] / it % 10)) {
  335. out << int32_t(number[i - 1] / it % 10);
  336. good = true;
  337. }
  338. it /= 10;
  339. }
  340. }
  341. return out;
  342. }
  343. };
  344.  
  345. struct Number2 {
  346. bool negative = false;
  347. vector<uint128> digits;
  348.  
  349. explicit Number2(uint128 x) {
  350. if (!(x >> 64)) {
  351. digits = {x};
  352. } else {
  353. while (x) {
  354. digits.push_back((uint64_t)x);
  355. x >>= 64;
  356. }
  357. }
  358. }
  359.  
  360. explicit Number2(string str) {
  361. Number10 num10(str);
  362. vector<int> tmp;
  363. while (num10.digits.size() > 2 || num10.digits[0] > 0) {
  364. tmp.push_back(num10 % 2);
  365. num10 = num10 / 2;
  366. }
  367. int cnt = 0;
  368. int value = 0;
  369. int multiplier = 1;
  370. for (auto& now : tmp) {
  371. if (cnt == 64) {
  372. digits.push_back(value);
  373. cnt = 0;
  374. value = 0;
  375. multiplier = 1;
  376. }
  377. value += now * multiplier;
  378. multiplier <<= 1;
  379. ++cnt;
  380. }
  381. digits.push_back(value);
  382. }
  383.  
  384. explicit Number2(const vector<uint128>& value) {
  385. digits = value;
  386. }
  387.  
  388. Number2& operator=(const Number2& other) = default;
  389.  
  390. const uint128& operator[](size_t ind) const {
  391. return digits[ind];
  392. }
  393.  
  394. size_t size() const {
  395. return digits.size();
  396. }
  397.  
  398. Number2 shift(size_t cnt) const {
  399. vector<uint128> result(cnt);
  400. for (auto& now: digits) {
  401. result.push_back(now);
  402. }
  403. return Number2(result);
  404. }
  405.  
  406. Number2 operator+(const Number2& other) const {
  407. if (other.negative) {
  408. return *this - (-other);
  409. }
  410. if (negative) {
  411. return other - (-*this);
  412. }
  413. vector<uint128> result(max(size(), other.size()));
  414. for (size_t i = 0; i < size(); ++i) {
  415. result[i] += digits[i];
  416. }
  417. for (size_t i = 0; i < other.size(); ++i) {
  418. result[i] += other[i];
  419. }
  420. for (size_t i = 0; i < result.size(); ++i) {
  421. if (result[i] >> 64) {
  422. if (i + 1 == result.size()) {
  423. result.push_back(0);
  424. }
  425. result[i + 1] += (result[i] >> 64);
  426. result[i] = uint64_t(result[i]);
  427. }
  428. }
  429. return Number2(result);
  430. }
  431.  
  432. Number2 operator-() const {
  433. Number2 x(digits);
  434. x.negative = !negative;
  435. return x;
  436. }
  437.  
  438. Number2 operator-(const Number2& other) const {
  439. if (other.negative) {
  440. return *this + (-other);
  441. }
  442. if (negative) {
  443. return -(other + (-*this));
  444. }
  445. if (*this >= other) {
  446. vector<int> result;
  447. for (auto& now : digits) {
  448. result.push_back(now);
  449. }
  450. for (size_t i = 0; i < other.size(); ++i) {
  451. result[i] -= other[i];
  452. }
  453. for (size_t i = 0; i + 1 < result.size(); ++i) {
  454. if (result[i] < 0) {
  455. result[i] += BASE2;
  456. result[i + 1] -= 1;
  457. }
  458. }
  459. while (result.size() > 1 && result.back() == 0) {
  460. result.pop_back();
  461. }
  462. vector<uint128> hm;
  463. for (auto& now : result) {
  464. hm.push_back(now);
  465. }
  466. return Number2(hm);
  467. } else {
  468. Number2 result(other - *this);
  469. result.negative = true;
  470. return result;
  471. }
  472. }
  473.  
  474. Number2& operator+=(const Number2& other) {
  475. return *this = *this + other;
  476. }
  477.  
  478. Number2& operator-=(const Number2& other) {
  479. return *this = *this - other;
  480. }
  481.  
  482. Number2 operator*(int value) const {
  483. vector<uint128> result(size());
  484. for (size_t i = 0; i < result.size(); ++i) {
  485. if (i < digits.size()) {
  486. result[i] += digits[i] * value;
  487. }
  488. if (result[i] >= BASE2 && i + 1 == result.size()) {
  489. result.push_back(0);
  490. }
  491. if (result[i] >= BASE2) {
  492. result[i + 1] += result[i] / BASE2;
  493. result[i] %= BASE2;
  494. }
  495. }
  496. return Number2(result);
  497. }
  498.  
  499. Number2 operator*(const Number2& other) const {
  500. Number2 result(string("0"));
  501. for (size_t i = 0; i < size(); ++i) {
  502. result += (other * digits[i]).shift(i);
  503. }
  504. result.negative = negative;
  505. if (other.negative) {
  506. result.negative = !result.negative;
  507. }
  508. return result;
  509. }
  510.  
  511. Number2 operator*=(const Number2& other) {
  512. return *this = *this * other;
  513. }
  514.  
  515. Number2 operator/(const Number2& other) const {
  516. Number2 number = *this;
  517. size_t cnt = number.size();
  518. vector<uint128> result(cnt);
  519. for (size_t i = cnt; i >= 1; --i) {
  520. auto it2 = other.shift(i - 1);
  521. uint128 rhs = other.digits.back();
  522. uint128 lhs = 0;
  523. if (other.size() + (i - 2) < number.size()) {
  524. lhs += number[other.size() + (i - 2)];
  525. }
  526. if (other.size() + (i - 1) < number.size()) {
  527. lhs += BASE2 * number[other.size() + (i - 1)];
  528. }
  529. uint128 x = (lhs + 1) / rhs;
  530. for (; x >= 1;) {
  531. auto it = it2 * x;
  532. if (number >= it) {
  533. number -= it;
  534. result[i - 1] += x;
  535. }
  536. if (x == 1) {
  537. break;
  538. }
  539. uint128 rhs = other.digits.back();
  540. uint128 lhs = 0;
  541. if (other.size() + (i - 2) < number.size()) {
  542. lhs += number[other.size() + (i - 2)];
  543. }
  544. if (other.size() + (i - 1) < number.size()) {
  545. lhs += BASE2 * number[other.size() + (i - 1)];
  546. }
  547. x = min((x + 1) / 2, (lhs + 1) / rhs);
  548. }
  549. }
  550. while (result.size() > 1 && result.back() == 0) {
  551. result.pop_back();
  552. }
  553. return Number2(result);
  554. }
  555.  
  556. Number2 operator%(const Number2& other) const {
  557. Number2 number = *this;
  558. size_t cnt = number.size();
  559. vector<int> result(cnt);
  560. for (size_t i = cnt; i >= 1; --i) {
  561. auto it2 = other.shift(i - 1);
  562. uint128 rhs = other.digits.back();
  563. uint128 lhs = 0;
  564. if (other.size() + (i - 2) < number.size()) {
  565. lhs += number[other.size() + (i - 2)];
  566. }
  567. if (other.size() + (i - 1) < number.size()) {
  568. lhs += BASE2 * number[other.size() + (i - 1)];
  569. }
  570. uint128 x = (lhs + 1) / rhs;
  571. for (; x >= 1;) {
  572. auto it = it2 * x;
  573. if (number >= it) {
  574. number -= it;
  575. result[i - 1] += x;
  576. }
  577. if (x == 1) {
  578. break;
  579. }
  580. uint128 rhs = other.digits.back();
  581. uint128 lhs = 0;
  582. if (other.size() + (i - 2) < number.size()) {
  583. lhs += number[other.size() + (i - 2)];
  584. }
  585. if (other.size() + (i - 1) < number.size()) {
  586. lhs += BASE2 * number[other.size() + (i - 1)];
  587. }
  588. x = min((x + 1) / 2, (lhs + 1) / rhs);
  589. }
  590. }
  591. while (result.size() > 1 && result.back() == 0) {
  592. result.pop_back();
  593. }
  594. return number;
  595. }
  596.  
  597. int operator%(int val) const {
  598. Number2 result = *this;
  599. int carry = 0;
  600. for (size_t i = result.size(); i >= 1; --i) {
  601. int cur = result[i - 1] + carry * 1ll * BASE2;
  602. result.digits[i - 1] = int(cur / val);
  603. carry = int(cur % val);
  604. }
  605. return carry;
  606. }
  607.  
  608. Number2 operator/(int val) const {
  609. Number2 result = *this;
  610. uint128 carry = 0;
  611. for (size_t i = result.size(); i >= 1; --i) {
  612. uint128 cur = result[i - 1] + carry * 1ll * BASE2;
  613. result.digits[i - 1] = uint128(cur / val);
  614. carry = uint128(cur % val);
  615. }
  616. while (result.digits.size() > 1 && result.digits.back() == 0) {
  617. result.digits.pop_back();
  618. }
  619. return result;
  620. }
  621.  
  622. bool operator<(const Number2& other) const {
  623. if (size() != other.size()) {
  624. return size() < other.size();
  625. }
  626. for (size_t i = size(); i >= 1; --i) {
  627. if (digits[i - 1] != other[i - 1]) {
  628. return digits[i - 1] < other[i - 1];
  629. }
  630. }
  631. return false;
  632. }
  633.  
  634. bool operator>(const Number2& other) const {
  635. return (other < *this);
  636. }
  637.  
  638. bool operator<=(const Number2& other) const {
  639. return !(*this > other);
  640. }
  641.  
  642. bool operator>=(const Number2& other) const {
  643. return !(*this < other);
  644. }
  645.  
  646. bool operator==(const Number2& other) const {
  647. return digits == other.digits;
  648. }
  649.  
  650. bool operator!=(const Number2& other) const {
  651. return !(*this == other);
  652. }
  653.  
  654. friend ostream& operator<<(ostream& out, const Number2& number) {
  655. Number2 num = number;
  656. vector<int> tmp;
  657. while (num.digits.size() > 2 || num.digits[0] > 0) {
  658. tmp.push_back(num % 10);
  659. num = num / 10;
  660. }
  661. reverse(tmp.begin(), tmp.end());
  662. for (auto& now : tmp) {
  663. out << uint64_t(now);
  664. }
  665. return out;
  666. }
  667. };
  668.  
  669. Number2 char_to_number(char symbol) {
  670. if (symbol >= 48 && symbol <= 57) {
  671. return Number2(symbol - 48);
  672. }
  673. if (symbol >= 65 && symbol <= 90) {
  674. return Number2(symbol - 55);
  675. }
  676. if (symbol >= 97 && symbol <= 122) {
  677. return Number2(symbol - 61);
  678. }
  679. if (symbol == 95) {
  680. return Number2(62);
  681. }
  682. if (symbol == 46) {
  683. return Number2(63);
  684. }
  685. throw runtime_error("Incorrect message");
  686. }
  687.  
  688. pair<Number2, Number2> division(const Number2& a, const Number2& b) {
  689. Number2 number = a;
  690. size_t cnt = number.size();
  691. vector<uint128> result(cnt);
  692. for (size_t i = cnt; i >= 1; --i) {
  693. auto it2 = b.shift(i - 1);
  694. int rhs = b.digits.back();
  695. int lhs = 0;
  696. if (b.size() + (i - 2) < number.size()) {
  697. lhs += number[b.size() + (i - 2)];
  698. }
  699. if (b.size() + (i - 1) < number.size()) {
  700. lhs += BASE2 * number[b.size() + (i - 1)];
  701. }
  702. int x = (lhs + 1) / rhs;
  703. for (; x >= 1;) {
  704. auto it = it2 * x;
  705. if (number >= it) {
  706. number -= it;
  707. result[i - 1] += x;
  708. }
  709. if (x == 1) {
  710. break;
  711. }
  712. int rhs = b.digits.back();
  713. int lhs = 0;
  714. if (b.size() + (i - 2) < number.size()) {
  715. lhs += number[b.size() + (i - 2)];
  716. }
  717. if (b.size() + (i - 1) < number.size()) {
  718. lhs += BASE2 * number[b.size() + (i - 1)];
  719. }
  720. x = min((x + 1) / 2, (lhs + 1) / rhs);
  721. }
  722. }
  723. while (result.size() > 1 && result.back() == 0) {
  724. result.pop_back();
  725. }
  726. return {Number2(result), number};
  727. }
  728.  
  729. const Number2 P(string("115792089210356248762697446949407573530086143415290314195533631308867097853951"));
  730. Number2 X(string("48439561293906451759052585252797914202762949526041747995844080717082404635286"));
  731. Number2 Y(string("36134250956749795798585127919587881956611106672985015071877198253568414405109"));
  732. Number2 ORD(string("115792089210356248762697446949407573529996955224135760342422259061068512044369"));
  733.  
  734. Number2 gcd(const Number2& a, const Number2& b, Number2& x, Number2& y) {
  735. if (a == Number2(0)) {
  736. x = Number2(0);
  737. y = Number2(1);
  738. return b;
  739. }
  740. auto it = division(b, a);
  741. Number2 x1(0), y1(0);
  742. Number2 g = gcd(it.second, a, x1, y1);
  743. x = y1 - (it.first) * x1;
  744. y = x1;
  745. return g;
  746. }
  747.  
  748.  
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!