結果

問題 No.781 円周上の格子点の数え上げ
ユーザー Min_25Min_25
提出日時 2019-09-22 18:53:56
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 4,581 bytes
コンパイル時間 640 ms
コンパイル使用メモリ 87,456 KB
最終ジャッジ日時 2023-10-19 07:22:08
合計ジャッジ時間 1,037 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:108:25: error: return type 'using Array = struct std::array<long long int, 769>' {aka 'struct std::array<long long int, 769>'} is incomplete
  108 | Array solve2(const i64 N) {
      |                         ^
main.cpp: In function 'void solve2(i64)':
main.cpp:110:9: error: variable 'Array ret' has initializer but incomplete type
  110 |   Array ret{};
      |         ^~~
main.cpp: In function 'i64 solve3(i64, i64)':
main.cpp:150:8: error: 'void ans_X' has incomplete type
  150 |   auto ans_X = solve2(X - 1);
      |        ^~~~~
main.cpp:151:8: error: 'void ans_Y' has incomplete type
  151 |   auto ans_Y = solve2(Y);
      |        ^~~~~

ソースコード

diff # 

#include <cstdio>
#include <cassert>
#include <cmath>
#include <cstring>

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <stack>
#include <queue>

#include <tuple>

#define getchar getchar_unlocked
#define putchar putchar_unlocked

#define _rep(_1, _2, _3, _4, name, ...) name
#define rep2(i, n) rep3(i, 0, n)
#define rep3(i, a, b) rep4(i, a, b, 1)
#define rep4(i, a, b, c) for (int i = int(a); i < int(b); i += int(c))
#define rep(...) _rep(__VA_ARGS__, rep4, rep3, rep2, _)(__VA_ARGS__)

using namespace std;

using i64 = long long;
using u8 = unsigned char;
using u32 = unsigned;
using u64 = unsigned long long;
using f80 = long double;

int get_int() {
  int n, c, sign = 0;
  while ((c = getchar()) < '-');
  if (c == '-') sign = 1, n = 0;
  else n = c - '0';
  while ((c = getchar()) >= '0') n = n * 10 + c - '0';
  return sign ? -n : n;
}

using i128 = __int128_t;
using u128 = __uint128_t;

inline int isqrt(i64 n) {
  return sqrtl(n);
}

class PrimeCount4 {
public:
  PrimeCount4(i64 N) 
      : sqrt_N(isqrt(N)), s1(sqrt_N + 1), s3(sqrt_N + 1),
                          l1(sqrt_N + 1), l3(sqrt_N + 1) {

    for (int i = 1; i <= sqrt_N; ++i) s1[i] = (i - 1) >> 2;
    for (int i = 1; i <= sqrt_N; ++i) l1[i] = (N / i - 1) >> 2;
    for (int i = 1; i <= sqrt_N; ++i) s3[i] = (i + 1) >> 2;
    for (int i = 1; i <= sqrt_N; ++i) l3[i] = (N / i + 1) >> 2;
    for (int p = 3; p <= sqrt_N; p += 2) if (s1[p] + s3[p] > s1[p - 1] + s3[p - 1]) {
      const i64 M = N / p, q = i64(p) * p;
      const int w = sqrt_N / p, v = min<i64>(sqrt_N, N / q);
      auto update = [&] (vector<int>& ds1, vector<int>& ds3, 
                         vector<i64>& dl1, vector<i64>& dl3) -> void {
        const int p1 = s1[p - 1];
        const int p3 = s3[p - 1];
        for (int i = 1; i <= w; ++i) {
          dl1[i] -= l1[i * p] - p1;
          dl3[i] -= l3[i * p] - p3;
        }
        const int t = min(isqrt(M), v);
        for (int i = w + 1; i <= t; ++i) {
          dl1[i] -= s1[M / i] - p1;
          dl3[i] -= s3[M / i] - p3;
        }
        for (int i = t + 1, q = M / i, r = M % i, c1 = s1[q] - p1, c3 = s3[q] - p3; i <= v; ++i, r -= q) {
          if (r < 0) r += i, --q, c1 = s1[q] - p1, c3 = s3[q] - p3;
          dl1[i] -= c1;
          dl3[i] -= c3;
        }
        for (int j = sqrt_N / p; j >= p; --j) {
          const int c1 = s1[j] - p1;
          const int c3 = s3[j] - p3;
          for (int i = j * p, e = min(sqrt_N + 1, (j + 1) * p); i < e; ++i) {
            ds1[i] -= c1;
            ds3[i] -= c3;
          }
        }
      };
      if ((p & 3) == 1) {
        update(s1, s3, l1, l3);
      } else {
        update(s3, s1, l3, l1);
      }
    }
  }
private:
  const int sqrt_N;

public:
  vector<int> s1, s3;
  vector<i64> l1, l3;
};

const int T = 768; // N <= 1e14
using Array = array<i64, T + 1>;

Array solve2(const i64 N) {
  assert(N <= i64(1e14));
  Array ret{};
  if (N >= 1) {
    auto pc = PrimeCount4(N);
    const int sqrt_N = isqrt(N);
    vector<int> primes;
    for (int i = 3; i <= sqrt_N; ++i) if (pc.s1[i] + pc.s3[i] > pc.s1[i - 1] + pc.s3[i - 1]) {
      primes.push_back(i);
    }
    primes.push_back(sqrt_N + 1);

    function< void(i64, int, int) > rec = [&] (i64 n, int beg, int coeff) -> void {
      const int below = primes[beg] - 1;
      ret[2 * coeff] += (n > sqrt_N ? pc.l1[N / n] : pc.s1[n]) - pc.s1[below];
      for (int pi = beg; pi < int(primes.size()); ++pi) {
        int p = primes[pi];
        if (i64(p) * p > n) break;
        i64 nn = n / p;
        if ((p & 3) == 1) {
          for (int e = 2; nn >= p; ) {
            rec(nn, pi + 1, coeff * e); e += 1;
            ret[coeff * e] += 1;
            nn /= p;
          }
        } else {
          while (nn >= p) {
            nn /= p;
            ret[coeff] += 1;
            if (nn < p) break;
            rec(nn, pi + 1, coeff);
            nn /= p;
          }
        }
      }
    };
    for (i64 n = N; n >= 1; n >>= 1) rec(n, 0, 1), ret[1] += 1;
  }
  return ret;
}

i64 solve3(i64 X, i64 Y) {
  auto ans_X = solve2(X - 1);
  auto ans_Y = solve2(Y);
  i64 ans = 0;
  for (int i = T; i >= 0; --i) {
    if (ans_Y[i] > ans_X[i]) {
      ans = i;
      break;
    }
  }
  return 4 * ans;
}

void solve() {
  i64 X, Y;
  while (~scanf("%lld %lld", &X, &Y)) {
    i64 ans = solve3(X, Y);
    printf("%lld\n", ans);
  }
}

int main() {
  clock_t beg = clock();
  solve();
  clock_t end = clock();
  fprintf(stderr, "%.3f sec\n", double(end - beg) / CLOCKS_PER_SEC);
  return 0;
}
0