Advertisement
Guest User

Untitled

a guest
Oct 19th, 2019
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 11.73 KB | None | 0 0
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5. long long n,s,odd,n1,s1,even;
  6.  
  7. const int base = 1000000000;
  8. const int base_digits = 9;
  9.  
  10. struct bigint {
  11. vector<int> z;
  12. int sign;
  13.  
  14. bigint() :
  15. sign(1) {
  16. }
  17.  
  18. bigint(long long v) {
  19. *this = v;
  20. }
  21.  
  22. bigint(const string &s) {
  23. read(s);
  24. }
  25.  
  26. void operator=(const bigint &v) {
  27. sign = v.sign;
  28. z = v.z;
  29. }
  30.  
  31. void operator=(long long v) {
  32. sign = 1;
  33. if (v < 0)
  34. sign = -1, v = -v;
  35. z.clear();
  36. for (; v > 0; v = v / base)
  37. z.push_back(v % base);
  38. }
  39.  
  40. bigint operator+(const bigint &v) const {
  41. if (sign == v.sign) {
  42. bigint res = v;
  43.  
  44. for (int i = 0, carry = 0; i < (int) max(z.size(), v.z.size()) || carry; ++i) {
  45. if (i == (int) res.z.size())
  46. res.z.push_back(0);
  47. res.z[i] += carry + (i < (int) z.size() ? z[i] : 0);
  48. carry = res.z[i] >= base;
  49. if (carry)
  50. res.z[i] -= base;
  51. }
  52. return res;
  53. }
  54. return *this - (-v);
  55. }
  56.  
  57. bigint operator-(const bigint &v) const {
  58. if (sign == v.sign) {
  59. if (abs() >= v.abs()) {
  60. bigint res = *this;
  61. for (int i = 0, carry = 0; i < (int) v.z.size() || carry; ++i) {
  62. res.z[i] -= carry + (i < (int) v.z.size() ? v.z[i] : 0);
  63. carry = res.z[i] < 0;
  64. if (carry)
  65. res.z[i] += base;
  66. }
  67. res.trim();
  68. return res;
  69. }
  70. return -(v - *this);
  71. }
  72. return *this + (-v);
  73. }
  74.  
  75. void operator*=(int v) {
  76. if (v < 0)
  77. sign = -sign, v = -v;
  78. for (int i = 0, carry = 0; i < (int) z.size() || carry; ++i) {
  79. if (i == (int) z.size())
  80. z.push_back(0);
  81. long long cur = z[i] * (long long) v + carry;
  82. carry = (int) (cur / base);
  83. z[i] = (int) (cur % base);
  84. //asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
  85. }
  86. trim();
  87. }
  88.  
  89. bigint operator*(int v) const {
  90. bigint res = *this;
  91. res *= v;
  92. return res;
  93. }
  94.  
  95. friend pair<bigint, bigint> divmod(const bigint &a1, const bigint &b1) {
  96. int norm = base / (b1.z.back() + 1);
  97. bigint a = a1.abs() * norm;
  98. bigint b = b1.abs() * norm;
  99. bigint q, r;
  100. q.z.resize(a.z.size());
  101.  
  102. for (int i = a.z.size() - 1; i >= 0; i--) {
  103. r *= base;
  104. r += a.z[i];
  105. int s1 = b.z.size() < r.z.size() ? r.z[b.z.size()] : 0;
  106. int s2 = b.z.size() - 1 < r.z.size() ? r.z[b.z.size() - 1] : 0;
  107. int d = ((long long) s1 * base + s2) / b.z.back();
  108. r -= b * d;
  109. while (r < 0)
  110. r += b, --d;
  111. q.z[i] = d;
  112. }
  113.  
  114. q.sign = a1.sign * b1.sign;
  115. r.sign = a1.sign;
  116. q.trim();
  117. r.trim();
  118. return make_pair(q, r / norm);
  119. }
  120.  
  121. friend bigint sqrt(const bigint &a1) {
  122. bigint a = a1;
  123. while (a.z.empty() || a.z.size() % 2 == 1)
  124. a.z.push_back(0);
  125.  
  126. int n = a.z.size();
  127.  
  128. int firstDigit = (int) sqrt((double) a.z[n - 1] * base + a.z[n - 2]);
  129. int norm = base / (firstDigit + 1);
  130. a *= norm;
  131. a *= norm;
  132. while (a.z.empty() || a.z.size() % 2 == 1)
  133. a.z.push_back(0);
  134.  
  135. bigint r = (long long) a.z[n - 1] * base + a.z[n - 2];
  136. firstDigit = (int) sqrt((double) a.z[n - 1] * base + a.z[n - 2]);
  137. int q = firstDigit;
  138. bigint res;
  139.  
  140. for(int j = n / 2 - 1; j >= 0; j--) {
  141. for(; ; --q) {
  142. bigint r1 = (r - (res * 2 * base + q) * q) * base * base + (j > 0 ? (long long) a.z[2 * j - 1] * base + a.z[2 * j - 2] : 0);
  143. if (r1 >= 0) {
  144. r = r1;
  145. break;
  146. }
  147. }
  148. res *= base;
  149. res += q;
  150.  
  151. if (j > 0) {
  152. int d1 = res.z.size() + 2 < r.z.size() ? r.z[res.z.size() + 2] : 0;
  153. int d2 = res.z.size() + 1 < r.z.size() ? r.z[res.z.size() + 1] : 0;
  154. int d3 = res.z.size() < r.z.size() ? r.z[res.z.size()] : 0;
  155. q = ((long long) d1 * base * base + (long long) d2 * base + d3) / (firstDigit * 2);
  156. }
  157. }
  158.  
  159. res.trim();
  160. return res / norm;
  161. }
  162.  
  163. bigint operator/(const bigint &v) const {
  164. return divmod(*this, v).first;
  165. }
  166.  
  167. bigint operator%(const bigint &v) const {
  168. return divmod(*this, v).second;
  169. }
  170.  
  171. void operator/=(int v) {
  172. if (v < 0)
  173. sign = -sign, v = -v;
  174. for (int i = (int) z.size() - 1, rem = 0; i >= 0; --i) {
  175. long long cur = z[i] + rem * (long long) base;
  176. z[i] = (int) (cur / v);
  177. rem = (int) (cur % v);
  178. }
  179. trim();
  180. }
  181.  
  182. bigint operator/(int v) const {
  183. bigint res = *this;
  184. res /= v;
  185. return res;
  186. }
  187.  
  188. int operator%(int v) const {
  189. if (v < 0)
  190. v = -v;
  191. int m = 0;
  192. for (int i = z.size() - 1; i >= 0; --i)
  193. m = (z[i] + m * (long long) base) % v;
  194. return m * sign;
  195. }
  196.  
  197. void operator+=(const bigint &v) {
  198. *this = *this + v;
  199. }
  200. void operator-=(const bigint &v) {
  201. *this = *this - v;
  202. }
  203. void operator*=(const bigint &v) {
  204. *this = *this * v;
  205. }
  206. void operator/=(const bigint &v) {
  207. *this = *this / v;
  208. }
  209.  
  210. bool operator<(const bigint &v) const {
  211. if (sign != v.sign)
  212. return sign < v.sign;
  213. if (z.size() != v.z.size())
  214. return z.size() * sign < v.z.size() * v.sign;
  215. for (int i = z.size() - 1; i >= 0; i--)
  216. if (z[i] != v.z[i])
  217. return z[i] * sign < v.z[i] * sign;
  218. return false;
  219. }
  220.  
  221. bool operator>(const bigint &v) const {
  222. return v < *this;
  223. }
  224. bool operator<=(const bigint &v) const {
  225. return !(v < *this);
  226. }
  227. bool operator>=(const bigint &v) const {
  228. return !(*this < v);
  229. }
  230. bool operator==(const bigint &v) const {
  231. return !(*this < v) && !(v < *this);
  232. }
  233. bool operator!=(const bigint &v) const {
  234. return *this < v || v < *this;
  235. }
  236.  
  237. void trim() {
  238. while (!z.empty() && z.back() == 0)
  239. z.pop_back();
  240. if (z.empty())
  241. sign = 1;
  242. }
  243.  
  244. bool isZero() const {
  245. return z.empty() || (z.size() == 1 && !z[0]);
  246. }
  247.  
  248. bigint operator-() const {
  249. bigint res = *this;
  250. res.sign = -sign;
  251. return res;
  252. }
  253.  
  254. bigint abs() const {
  255. bigint res = *this;
  256. res.sign *= res.sign;
  257. return res;
  258. }
  259.  
  260. long long longValue() const {
  261. long long res = 0;
  262. for (int i = z.size() - 1; i >= 0; i--)
  263. res = res * base + z[i];
  264. return res * sign;
  265. }
  266.  
  267. friend bigint gcd(const bigint &a, const bigint &b) {
  268. return b.isZero() ? a : gcd(b, a % b);
  269. }
  270. friend bigint lcm(const bigint &a, const bigint &b) {
  271. return a / gcd(a, b) * b;
  272. }
  273.  
  274. void read(const string &s) {
  275. sign = 1;
  276. z.clear();
  277. int pos = 0;
  278. while (pos < (int) s.size() && (s[pos] == '-' || s[pos] == '+')) {
  279. if (s[pos] == '-')
  280. sign = -sign;
  281. ++pos;
  282. }
  283. for (int i = s.size() - 1; i >= pos; i -= base_digits) {
  284. int x = 0;
  285. for (int j = max(pos, i - base_digits + 1); j <= i; j++)
  286. x = x * 10 + s[j] - '0';
  287. z.push_back(x);
  288. }
  289. trim();
  290. }
  291.  
  292. friend istream& operator>>(istream &stream, bigint &v) {
  293. string s;
  294. stream >> s;
  295. v.read(s);
  296. return stream;
  297. }
  298.  
  299. friend ostream& operator<<(ostream &stream, const bigint &v) {
  300. if (v.sign == -1)
  301. stream << '-';
  302. stream << (v.z.empty() ? 0 : v.z.back());
  303. for (int i = (int) v.z.size() - 2; i >= 0; --i)
  304. stream << setw(base_digits) << setfill('0') << v.z[i];
  305. return stream;
  306. }
  307.  
  308. static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits) {
  309. vector<long long> p(max(old_digits, new_digits) + 1);
  310. p[0] = 1;
  311. for (int i = 1; i < (int) p.size(); i++)
  312. p[i] = p[i - 1] * 10;
  313. vector<int> res;
  314. long long cur = 0;
  315. int cur_digits = 0;
  316. for (int i = 0; i < (int) a.size(); i++) {
  317. cur += a[i] * p[cur_digits];
  318. cur_digits += old_digits;
  319. while (cur_digits >= new_digits) {
  320. res.push_back(int(cur % p[new_digits]));
  321. cur /= p[new_digits];
  322. cur_digits -= new_digits;
  323. }
  324. }
  325. res.push_back((int) cur);
  326. while (!res.empty() && res.back() == 0)
  327. res.pop_back();
  328. return res;
  329. }
  330.  
  331. typedef vector<long long> vll;
  332.  
  333. static vll karatsubaMultiply(const vll &a, const vll &b) {
  334. int n = a.size();
  335. vll res(n + n);
  336. if (n <= 32) {
  337. for (int i = 0; i < n; i++)
  338. for (int j = 0; j < n; j++)
  339. res[i + j] += a[i] * b[j];
  340. return res;
  341. }
  342.  
  343. int k = n >> 1;
  344. vll a1(a.begin(), a.begin() + k);
  345. vll a2(a.begin() + k, a.end());
  346. vll b1(b.begin(), b.begin() + k);
  347. vll b2(b.begin() + k, b.end());
  348.  
  349. vll a1b1 = karatsubaMultiply(a1, b1);
  350. vll a2b2 = karatsubaMultiply(a2, b2);
  351.  
  352. for (int i = 0; i < k; i++)
  353. a2[i] += a1[i];
  354. for (int i = 0; i < k; i++)
  355. b2[i] += b1[i];
  356.  
  357. vll r = karatsubaMultiply(a2, b2);
  358. for (int i = 0; i < (int) a1b1.size(); i++)
  359. r[i] -= a1b1[i];
  360. for (int i = 0; i < (int) a2b2.size(); i++)
  361. r[i] -= a2b2[i];
  362.  
  363. for (int i = 0; i < (int) r.size(); i++)
  364. res[i + k] += r[i];
  365. for (int i = 0; i < (int) a1b1.size(); i++)
  366. res[i] += a1b1[i];
  367. for (int i = 0; i < (int) a2b2.size(); i++)
  368. res[i + n] += a2b2[i];
  369. return res;
  370. }
  371.  
  372. bigint operator*(const bigint &v) const {
  373. vector<int> a6 = convert_base(this->z, base_digits, 6);
  374. vector<int> b6 = convert_base(v.z, base_digits, 6);
  375. vll a(a6.begin(), a6.end());
  376. vll b(b6.begin(), b6.end());
  377. while (a.size() < b.size())
  378. a.push_back(0);
  379. while (b.size() < a.size())
  380. b.push_back(0);
  381. while (a.size() & (a.size() - 1))
  382. a.push_back(0), b.push_back(0);
  383. vll c = karatsubaMultiply(a, b);
  384. bigint res;
  385. res.sign = sign * v.sign;
  386. for (int i = 0, carry = 0; i < (int) c.size(); i++) {
  387. long long cur = c[i] + carry;
  388. res.z.push_back((int) (cur % 1000000));
  389. carry = (int) (cur / 1000000);
  390. }
  391. res.z = convert_base(res.z, 6, base_digits);
  392. res.trim();
  393. return res;
  394. }
  395. };
  396. bigint solve2()
  397. {
  398. bigint evenCnt = n / 2;
  399. bigint oddCnt = (n + 1) / 2;
  400. bigint evenSum = (evenCnt * ((bigint)4 + (evenCnt - (bigint)1) * (bigint)2)) / (bigint)2;
  401. bigint oddSum = (oddCnt * ((bigint)2 + (oddCnt - (bigint)1) * (bigint)2)) / (bigint)2;
  402. bigint diff = evenSum - oddSum;
  403. if(diff < 0)
  404. diff *= -1;
  405. return diff;
  406. }
  407. int main()
  408. {
  409. cin>>n;
  410. cout << solve2();
  411. return 0;
  412. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement