結果

問題 No.886 Direct
ユーザー Min_25Min_25
提出日時 2019-09-15 09:34:18
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 10 ms / 4,000 ms
コード長 4,146 bytes
コンパイル時間 853 ms
コンパイル使用メモリ 99,748 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-06 22:40:04
合計ジャッジ時間 1,899 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,812 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 1 ms
6,940 KB
testcase_08 AC 1 ms
6,944 KB
testcase_09 AC 1 ms
6,940 KB
testcase_10 AC 1 ms
6,944 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 1 ms
6,944 KB
testcase_13 AC 2 ms
6,940 KB
testcase_14 AC 2 ms
6,940 KB
testcase_15 AC 1 ms
6,944 KB
testcase_16 AC 1 ms
6,940 KB
testcase_17 AC 2 ms
6,940 KB
testcase_18 AC 2 ms
6,940 KB
testcase_19 AC 2 ms
6,940 KB
testcase_20 AC 2 ms
6,940 KB
testcase_21 AC 2 ms
6,944 KB
testcase_22 AC 1 ms
6,940 KB
testcase_23 AC 4 ms
6,944 KB
testcase_24 AC 6 ms
6,940 KB
testcase_25 AC 4 ms
6,940 KB
testcase_26 AC 5 ms
6,940 KB
testcase_27 AC 8 ms
6,944 KB
testcase_28 AC 7 ms
6,940 KB
testcase_29 AC 1 ms
6,940 KB
testcase_30 AC 2 ms
6,940 KB
testcase_31 AC 10 ms
6,944 KB
testcase_32 AC 9 ms
6,940 KB
testcase_33 AC 9 ms
6,940 KB
testcase_34 AC 9 ms
6,940 KB
testcase_35 AC 9 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

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 u128 = __uint128_t;
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;
}

int isqrt(i64 N) {
  return sqrtl(N);
}

template <typename T, typename Integer>
T fast_sum(Integer N, Integer M) {
  if (N < M) swap(N, M);
  if (M == 0) return T(N, M);
  const int vN = isqrt(N), wN = max<int>(1, N / (vN + 1));
  const int vM = max<int>(1, M / wN);

  vector<T> larges(wN + 1);
  vector<T> smalls(vN + vM);
  vector<int> offset(vN + 2, -2); int o = 0;
  auto memo = [&] (int n, int m, const T& v) {
    if (m == 0) return;
    if (offset[n] == -2) offset[n] = o - m;
    smalls[o++] = v;
  };
  auto cache = [&] (int n, int m) -> T {
    return (m == 0) ? T(n, m) : smalls[offset[n] + m];
  };
  
  vector<Integer> qn(vN + 2), qm(vM + 2);
  auto calc = [&] (const Integer n, const Integer m, const Integer k) -> T {
    auto ret = T(n, m);
    if (n <= 1 || m == 0) return ret;
    const int vn = isqrt(n), wn = n / (vn + 1), vm = max<int>(1, m / wn);
    for (int i = 1; i <= vn + 1; ++i) qn[i] = n / i;
    for (int i = 1; i <= vm + 1; ++i) qm[i] = m / i;
    for (int n2 = 1, m2 = m / n; n2 <= vn; ++n2) {
      if (qm[m2 + 1] >= qn[n2 + 1]) {
        ret -= cache(n2, m2).sum(qm[m2 + 1], qn[n2]); ++m2;
        ret -= cache(n2, m2).sum(qn[n2 + 1], qm[m2]);
      } else {
        ret -= cache(n2, m2).sum(qn[n2 + 1], qn[n2]);
      }
    }
    for (int i = 2; i <= wn; ++i) {
      ret -= (i * k <= wN ? larges[i * k] : cache(n / i, m / i)).sum(i - 1, i);
    }
    return ret;
  };

  vector<Integer> qN(vN + 2), qM(vM + 2); qM[0] = N;
  for (int i = 1; i <= vN + 1; ++i) qN[i] = N / i;
  for (int i = 1; i <= vM + 1; ++i) qM[i] = M / i;
  for (int n = 1, m = M / N; n <= vN; ++n) {
    if (qM[m + 1] >= qN[n + 1]) memo(n, m, calc(n, m, wN + 1)), ++m;
    memo(n, m, calc(n, m, wN + 1));
  }
  for (int k = wN; k >= 1; --k) larges[k] = calc(N / k, M / k, k);
  return larges[1];
}

struct Sum {
  static constexpr u64 S1(u64 n) { return u64(n) * (n + 1) >> 1; }
  static constexpr u64 S2(u64 n) { 
    return n >= 2000000 ? u128(n) * (n + 1) * (2 * n + 1) / 6 : n * (n + 1) * (2 * n + 1) / 6;
  }
  Sum() : Sum(0, 0) {}
  Sum(int N, int M) 
    : s00(u64(N) * M), s01(u64(N) * S1(M)), s10(S1(N) * M), s11(u128(S1(N)) * S1(M)) {}
  Sum sum(i64 a, i64 b) const {
    // (a, b]
    auto ret = Sum(*this);
    ret.s00 *= (b - a);
    auto c1 = S1(b) - S1(a);
    ret.s01 *= c1; ret.s10 *= c1;
    ret.s11 *= S2(b) - S2(a);
    return ret;
  }
  Sum& operator -= (const Sum& rhs) {
    s00 -= rhs.s00; s01 -= rhs.s01; s10 -= rhs.s10; s11 -= rhs.s11;
    return *this;
  }
  Sum operator - (const Sum& rhs) const { return Sum(*this) -= rhs; }
  u64 s00, s01, s10;
  u128 s11;
};

u128 fast(int N, int M) {
  if (N < M) swap(N, M);
  auto ans = fast_sum<Sum, int>(N - 1, M - 1);
  u128 ret = u128(ans.s00) * N * M - u128(ans.s01) * N - u128(ans.s10) * M + ans.s11;
  return ret * 2 + u64(N - 1) * M + u64(N) * (M - 1);
}

void solve() {
  const int mod = 1e9 + 7;
  int N, M;
  while (~scanf("%d %d", &N, &M)) {
    assert(N <= 3000000 && M <= 3000000);
    auto ans = fast(N, M);
    printf("%llu\n", u64(ans % mod));
  }
}

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