Advertisement
Guest User

Untitled

a guest
Nov 13th, 2019
138
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.99 KB | None | 0 0
  1. // #define PIHAYEM_S_NOGI 1
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #ifdef PIHAYEM_S_NOGI
  5. #pragma GCC optimize("Ofast")
  6. #pragma GCC optimize("no-stack-protector")
  7. #pragma GCC optimize("unroll-loops")
  8. #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
  9. #pragma GCC optimize("fast-math")
  10. #include <ext/pb_ds/assoc_container.hpp>
  11. using namespace __gnu_pbds;
  12. #define unordered_map gp_hash_table
  13. #endif
  14. #define dbg(x) cout << __func__ << ':' << __LINE__ << ' ' << #x << " = " << x << endl
  15. #define endl '\n'
  16. #define sqr(x) (x) * (x)
  17. #define int long long
  18. #define ll long long
  19. // #define double long double
  20. #define eb emplace_back
  21. #define pb push_back
  22. #define f first
  23. #define fr(s) freopen(s, "r", stdin)
  24. #define fw(s) freopen(s, "w", stdout)
  25. #define pll pair<long long, long long>
  26. #define s second
  27. #define all(x) x.begin(), x.end()
  28. #define vi vector <int>
  29. #define pii pair <int, int>
  30. #define mp(a, b) make_pair(a, b)
  31. #define forn(i, from, n) for (int i = (int)(from); i < (int)(n); ++i)
  32.  
  33. ostream &operator<<(ostream &out, const __int128_t a){
  34. out << (int)a;
  35. return out;
  36. }
  37.  
  38. __int128_t sqrtt(__int128_t n){
  39. __int128_t l = 0, r = n;
  40. while(r - l > 1){
  41. // cout << l << ' '
  42. __int128_t m = (l + r) / 2;
  43. if(m * m > n) r = m;
  44. else l = m;
  45. }
  46. return l;
  47. }
  48.  
  49. signed main() {
  50. #ifdef DEBUG
  51. fr("input.txt");
  52. // fw("output.txt");
  53. #else
  54. #endif
  55. ios_base::sync_with_stdio(false);
  56. cin.tie(0);
  57. cout.tie(0);
  58. int nn;
  59. cin >> nn;
  60. __int128_t n = nn;
  61. __int128_t sq = sqrtt(n);
  62. if(sq * sq == n){
  63. if(sq % 2){
  64. cout << sq << ' ' << sq;
  65. return 0;
  66. }
  67. if((sq / 2) % 2){
  68. cout << 1 << ' ' << sq;
  69. return 0;
  70. } else{
  71. cout << sq << ' ' << 1;
  72. return 0;
  73. }
  74. }
  75. // cout << sq << endl;
  76. __int128_t ssq = sq / 2 * 2 + 1;
  77. if((sq / 2) % 2 == 0){
  78. // cout << n << ' ' << sqr(sq / 2 * 2 + 1) << endl;
  79. if(n >= sqr(sq / 2 * 2 + 1)){
  80. if(n == sqr(sq / 2 * 2 + 1)){
  81. cout << ssq << ' ' << ssq << endl;
  82. return 0;
  83. }
  84. if(n - 1 == sqr(sq / 2 * 2 + 1)){
  85. cout << ssq + 1 << ' ' << ssq << endl;
  86. return 0;
  87. }
  88. if(n - 2 == sqr(sq / 2 * 2 + 1)){
  89. cout << ssq + 1 << ' ' << ssq + 1 << endl;
  90. return 0;
  91. }
  92. if(n - 3 == sqr(sq / 2 * 2 + 1)){
  93. cout << ssq << ' ' << ssq + 1 << endl;
  94. return 0;
  95. }
  96. __int128_t k = n - sqr(sq / 2 * 2 + 1);
  97. if(k % 4 == 0){
  98. cout << ssq - k / 4 * 2 + 1 << ' ' << ssq + 1 << endl;
  99. return 0;
  100. } else if(k % 4 == 1){
  101. cout << ssq - k / 4 * 2 + 1 << ' ' << ssq << endl;
  102. return 0;
  103. } else if(k % 4 == 2){
  104. cout << ssq - k / 4 * 2 << ' ' << ssq << endl;
  105. return 0;
  106. } else cout << ssq - k / 4 * 2 << ' ' << ssq + 1 << endl;
  107. } else{
  108. __int128_t k = sqr(sq / 2 * 2 + 1) - n;
  109. // cout << sqr(sq / 2 * 2 + 1) << ' ' << k << endl;
  110. if(k % 4 <= 1) cout << ssq;
  111. else cout << ssq + 1;
  112. cout << ' ';
  113. cout << ssq - (k - 1) / 2 - 1 << endl;
  114. return 0;
  115. }
  116. } else{
  117. if(n - 3 <= sqr(sq / 2 * 2 + 1)){
  118. // cout << 'x';
  119. if(n == sqr(sq / 2 * 2 + 1)){
  120. cout << ssq << ' ' << ssq << endl;
  121. return 0;
  122. }
  123. if(n - 1 == sqr(sq / 2 * 2 + 1)){
  124. cout << ssq << ' ' << ssq + 1 << endl;
  125. return 0;
  126. }
  127. if(n - 2 == sqr(sq / 2 * 2 + 1)){
  128. cout << ssq + 1 << ' ' << ssq + 1 << endl;
  129. return 0;
  130. }
  131. if(n - 3 == sqr(sq / 2 * 2 + 1)){
  132. cout << ssq + 1 << ' ' << ssq << endl;
  133. return 0;
  134. }
  135. __int128_t k = sqr(sq / 2 * 2 + 1) - n - 1 + 4;
  136. // cout << k << endl;
  137. if(k % 4 == 0){
  138. cout << ssq - k / 4 * 2 + 1 << ' ' << ssq << endl;
  139. return 0;
  140. } else if(k % 4 == 1){
  141. cout << ssq - k / 4 * 2 + 1 << ' ' << ssq + 1 << endl;
  142. return 0;
  143. } else if(k % 4 == 2){
  144. cout << ssq - k / 4 * 2 << ' ' << ssq + 1 << endl;
  145. return 0;
  146. } else cout << ssq - k / 4 * 2 << ' ' << ssq << endl;
  147. } else{
  148. __int128_t k = n - sqr(sq / 2 * 2 + 1);
  149. // cout << k << ' ' << ssq << endl;
  150. if(k % 4 == 0 || k % 4 == 3) cout << ssq + 1;
  151. else cout << ssq;
  152. cout << ' ';
  153. cout << ssq - (k - 4) / 2 - 1 << endl;
  154. return 0;
  155. }
  156. }
  157. return 0;
  158. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement