Advertisement
Um_nik

Untitled

May 14th, 2022
1,094
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <vector>
  7. #include <set>
  8. #include <map>
  9. #include <unordered_set>
  10. #include <unordered_map>
  11. #include <queue>
  12. #include <ctime>
  13. #include <cassert>
  14. #include <complex>
  15. #include <string>
  16. #include <cstring>
  17. #include <chrono>
  18. #include <random>
  19. #include <bitset>
  20. #include <array>
  21. using namespace std;
  22.  
  23. #ifdef LOCAL
  24.     #define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
  25. #else
  26.     #define eprintf(...) 42
  27. #endif
  28.  
  29. using ll = long long;
  30. using ld = long double;
  31. using uint = unsigned int;
  32. using ull = unsigned long long;
  33. template<typename T>
  34. using pair2 = pair<T, T>;
  35. using pii = pair<int, int>;
  36. using pli = pair<ll, int>;
  37. using pll = pair<ll, ll>;
  38. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  39. ll myRand(ll B) {
  40.     return (ull)rng() % B;
  41. }
  42.  
  43. #define pb push_back
  44. #define mp make_pair
  45. #define all(x) (x).begin(),(x).end()
  46. #define fi first
  47. #define se second
  48.  
  49. clock_t startTime;
  50. double getCurrentTime() {
  51.     return (double)(clock() - startTime) / CLOCKS_PER_SEC;
  52. }
  53.  
  54. const int N = (int)1e5 + 1;
  55. //const int N = (int)1e3 + 1;
  56. ll ans[N + 11];
  57.  
  58. int main()
  59. {
  60.     startTime = clock();
  61. //  freopen("input.txt", "r", stdin);
  62. //  freopen("output.txt", "w", stdout);
  63.  
  64.     for (ll y = 1; y < N; y++) {
  65.         if (y % 1000 == 0) eprintf("y = %lld, time = %.5lf\n", y, getCurrentTime());
  66.         ll R = y;
  67.         ll x2y2 = y * y;
  68.         ll R2R = R * R + R;
  69.         for (ll x = 1; x <= y; x++) {
  70.             x2y2 += x + x - 1;
  71.             while(R2R < x2y2) {
  72.                 R++;
  73.                 R2R += R + R;
  74.             }
  75.             if (R >= N) break;
  76.             ll z = x2y2 - R2R + R;
  77.             if (z > 0) {
  78.                 if (z >= y && z <= R + R - y) {
  79.                     ans[R] += 1 + (int)(x != y);
  80.                 }
  81.             } else {
  82.                 z += R + R - 1;
  83.                 if (z >= y && z <= R + R - 2 - y) {
  84.                     ans[R] += 1 + (int)(x != y);
  85.                 }
  86.             }
  87.         }
  88.     }
  89.     for (int i = 1; i <= N; i++)
  90.         ans[i] += ans[i - 1];
  91.  
  92.     int t;
  93.     scanf("%d", &t);
  94.     for (int i = 1; i <= t; i++) {
  95.         int n;
  96.         scanf("%d", &n);
  97.         printf("Case #%d: %lld\n", i, 4 * ans[n]);
  98.     }
  99.  
  100.     return 0;
  101. }
  102.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement