結果

問題 No.886 Direct
ユーザー Min_25Min_25
提出日時 2019-09-14 23:34:19
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 25 ms / 4,000 ms
コード長 4,239 bytes
コンパイル時間 1,241 ms
コンパイル使用メモリ 100,292 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-06 22:11:29
合計ジャッジ時間 2,350 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 1 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 1 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 1 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 1 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 1 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
testcase_23 AC 11 ms
5,376 KB
testcase_24 AC 13 ms
5,376 KB
testcase_25 AC 9 ms
5,376 KB
testcase_26 AC 10 ms
5,376 KB
testcase_27 AC 21 ms
5,376 KB
testcase_28 AC 22 ms
5,376 KB
testcase_29 AC 1 ms
5,376 KB
testcase_30 AC 2 ms
5,376 KB
testcase_31 AC 25 ms
5,376 KB
testcase_32 AC 25 ms
5,376 KB
testcase_33 AC 25 ms
5,376 KB
testcase_34 AC 25 ms
5,376 KB
testcase_35 AC 25 ms
5,376 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>
T fast_sum(i64 N, i64 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> lN(wN + 1);
  vector<T> memo(vN + vM);
  vector<int> offset(vN + 2, -2); int o = 0;
  auto memoize = [&] (int n, int m, const T& v) {
    if (m == 0) return;
    if (offset[n] == -2) offset[n] = o - m;
    memo[o++] = v;
  };
  auto cache = [&] (int n, int m) -> T {
    return (m == 0) ? T(n, m) : memo[offset[n] + m];
  };
  
  vector<i64> qn(vN + 2), qm(vM + 2);
  auto calc = [&] (const i64 n, const i64 m, const i64 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 ? lN[i * k] : cache(n / i, m / i)).sum(i - 1, i);
    }
    return ret;
  };

  vector<i64> 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]) memoize(n, m, calc(n, m, wN + 1)), ++m;
    memoize(n, m, calc(n, m, wN + 1));
  }
  for (int k = wN; k >= 1; --k) lN[k] = calc(N / k, M / k, k);
  return lN[1];
}

struct Sum {
  static constexpr u128 S1(u64 n) { return u128(n) * (n + 1) >> 1; }
  static constexpr u128 S2(u64 n) { return u128(n) * (n + 1) * (2 * n + 1) / 6; }
  Sum() : Sum(0, 0) {}
  Sum(i64 N, i64 M) 
    : s00(u128(N) * M), s01(u128(N) * S1(M)), s10(S1(N) * M), s11(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; }
  u128 s00, s01, s10, s11;
};

u128 naive(i64 N, i64 M) {
  u128 ans = 0;
  for (int dy = 1; dy < N; ++dy) {
    for (int dx = 1; dx < M; ++dx) {
      int g = __gcd(dx, dy) == 1;
      ans += u128(M - dx) * (N - dy) * g;
    }
  }
  ans *= 2;
  ans += u128(N - 1) * M + u128(N) * (M - 1);
  return ans;
}

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

void solve() {
  const int mod = 1e9 + 7;
  int N, M;
  while (~scanf("%d %d", &N, &M)) {
    auto ans = fast(N, M);
    printf("%llu\n", i64(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