結果

問題 No.1627 三角形の成立
ユーザー noshi91
提出日時 2021-07-23 22:45:07
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 58 ms / 1,000 ms
コード長 3,300 bytes
コンパイル時間 753 ms
コンパイル使用メモリ 84,528 KB
最終ジャッジ日時 2025-01-23 08:29:10
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cassert>
#include <cstddef>
#include <numeric>
#include <utility>
#include <vector>

namespace n91 {

class prime_sieve {
public:
  using size_type = std::size_t;

private:
  std::vector<size_type> prime, factor;

public:
  prime_sieve() {}
  explicit prime_sieve(const size_type size) : prime(), factor(size) {
    if (size == 0) {
      return;
    }
    std::iota(factor.begin(), factor.end(), static_cast<size_type>(0));
    factor[0] = 1;
    if (size == 1) {
      return;
    }
    factor[1] = 0;
    prime.reserve(size);
    for (size_type i{2}; i != size; ++i) {
      const size_type fi{factor[i]};
      if (fi == i) {
        prime.push_back(i);
      }
      for (const size_type p : prime) {
        if (p > fi) {
          break;
        }
        const size_type ip{i * p};
        if (ip >= size) {
          break;
        }
        factor[ip] = p;
      }
    }
    prime.shrink_to_fit();
  }
  size_type len() const noexcept { return factor.size(); }
  bool is_prime(const size_type i) const noexcept {
    assert(i < len());
    return factor[i] == i;
  }
  std::vector<size_type> factorize(size_type i) const noexcept {
    assert(i != 0);
    std::vector<size_type> ret;
    while (i != 1) {
      ret.push_back(factor[i]);
      i /= factor[i];
    }
    return std::move(ret);
  }
  template <class C> void divisor_zeta(C &c) const noexcept {
    const size_type n{c.size()};
    assert(n <= len());
    for (size_type i{0}; i != prime.size() && prime[i] < n; ++i) {
      for (size_type j{1}; j * prime[i] < n; ++j) {
        c[j * prime[i]] += c[j];
      }
    }
  }
  template <class C> void divisor_mobius(C &c) const noexcept {
    const size_type n{c.size()};
    assert(n <= len());
    for (size_type i{0}; i != prime.size() && prime[i] < n; ++i) {
      for (size_type j{(n - 1) / prime[i]}; j != 0; --j) {
        c[j * prime[i]] -= c[j];
      }
    }
  }
  template <class C> void multiple_zeta(C &c) const noexcept {
    const size_type n{c.size()};
    assert(n <= len());
    for (size_type i{0}; i != prime.size() && prime[i] < n; ++i) {
      for (size_type j{(n - 1) / prime[i]}; j != 0; --j) {
        c[j] += c[j * prime[i]];
      }
    }
  }
  template <class C> void multiple_mobius(C &c) const noexcept {
    const size_type n{c.size()};
    assert(n <= len());
    for (size_type i{0}; i != prime.size() && prime[i] < n; ++i) {
      for (size_type j{1}; j * prime[i] < n; ++j) {
        c[j] -= c[j * prime[i]];
      }
    }
  }
};

} // namespace n91

#include <algorithm>
#include <iostream>
#include <vector>

#include <atcoder/modint>

int main() {
  using mint = atcoder::modint1000000007;

  int n, m;
  std::cin >> n >> m;

  int A = std::max(n, m);
  std::vector<mint> a(A, 0);
  const mint inv2 = mint(1) / 2;
  for (int d = 1; d != A; d += 1) {
    mint h = 0, v = 0;
    {
      mint x = (n - 1) / d;
      h = x * n - d * x * (x + 1) * inv2;
    }
    {
      mint x = (m - 1) / d;
      v = x * m - d * x * (x + 1) * inv2;
    }
    a[d] = 2 * h * v + n * v + m * h;
  }
  n91::prime_sieve(A).multiple_mobius(a);

  mint ans = [&]() {
    mint x = mint(n) * m;
    return x * (x - 1) * (x - 2) / 6;
  }();

  for (int d = 1; d != A; d += 1) {
    ans -= a[d] * (d - 1);
  }

  std::cout << ans.val() << "\n";

  return 0;
}
0