QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#209112#3681. 模积和KHIN100 ✓4ms3732kbC++175.7kb2023-10-10 10:17:382023-10-10 10:17:38

Judging History

你现在查看的是最新测评结果

  • [2023-10-10 10:17:38]
  • 评测
  • 测评结果:100
  • 用时:4ms
  • 内存:3732kb
  • [2023-10-10 10:17:38]
  • 提交

answer

# include <bits/stdc++.h>

using namespace std;

namespace kh {
  constexpr int P(19'940'417);
  inline namespace src {
    template <typename T>
      constexpr auto cmin(T& a, T const& b) {
        if (b < a) return pair<T&, bool>(a = b, true);
        else return pair<T&, bool>(a, false);
      }
    template <typename T>
      constexpr auto cmax(T& a, T const& b) {
        if (a < b) return pair<T&, bool>(a = b, true);
        else return pair<T&, bool>(a, false);
      }
    template <typename T>
      constexpr auto cminmax(T& a, T& b) {
        bool const swp(b < a ? swap(a, b), true : false);
        return make_pair(pair<T&, T&>(a, b), swp);
      }
    template <typename T, class Compare>
      constexpr auto cmin(T& a, T const& b, Compare comp) {
        if (comp(b, a)) return pair<T&, bool>(a = b, true);
        else return pair<T&, bool>(a, false);
      }
    template <typename T, class Compare>
      constexpr auto cmax(T& a, T const& b, Compare comp) {
        if (comp(a, b)) return pair<T&, bool>(a = b, true);
        else return pair<T&, bool>(a, false);
      }
    template <typename T, class Compare>
      constexpr auto cminmax(T& a, T& b, Compare comp) {
        bool const swp(comp(b, a) ? swap(a, b), true : false);
        return make_pair(pair<T&, T&>(a, b), swp);
      }
    template <typename T>
      constexpr int sgn(T const x)
      { return (x > 0) - (x < 0); }
    template <typename T>
      struct frac {
        T num, den;
        constexpr frac(T const n = 0, T const d = 1)
          : num(n / __gcd(n, d)), den(d / __gcd(n, d))
        { assert(den), num *= sgn(den), den *= sgn(den); }
        constexpr frac& operator+=(frac const b) { return *this = *this + b; }
        constexpr frac& operator-=(frac const b) { return *this = *this - b; }
        constexpr frac& operator*=(frac const b) { return *this = *this * b; }
        constexpr frac& operator/=(frac const b) { return *this = *this / b; }
        constexpr frac& operator++() { return num += den, *this; }
        constexpr frac& operator--() { return num -= den, *this; }
        constexpr frac operator++(int) { return num += den, *this - 1; }
        constexpr frac operator--(int) { return num -= den, *this - 1; }
        constexpr frac operator+() const { return frac(+num, den); }
        constexpr frac operator-() const { return frac(-num, den); }
        friend constexpr frac operator+(frac const a, frac const b)
        { return frac(a.num * b.den + b.num * a.den, a.den * b.den); }
        friend constexpr frac operator-(frac const a, frac const b)
        { return frac(a.num * b.den - b.num * a.den, a.den * b.den); }
        friend constexpr frac operator*(frac const a, frac const b)
        { return frac(a.num * b.num, a.den * b.den); }
        friend constexpr frac operator/(frac const a, frac const b)
        { return frac(a.num * b.den, a.den * b.num); }
        friend constexpr bool operator==(frac const a, frac const b)
        { return a.num * b.den == b.num * a.den; }
        friend constexpr bool operator!=(frac const a, frac const b)
        { return a.num * b.den != b.num * a.den; }
        friend constexpr bool operator<(frac const a, frac const b)
        { return a.num * b.den < b.num * a.den; }
        friend constexpr bool operator>(frac const a, frac const b)
        { return a.num * b.den > b.num * a.den; }
        friend constexpr bool operator<=(frac const a, frac const b)
        { return a.num * b.den <= b.num * a.den; }
        friend constexpr bool operator>=(frac const a, frac const b)
        { return a.num * b.den >= b.num * a.den; }
      };
    constexpr int pow(int a, int n) {
      int r(1);
      while (n) {
        r = 1l * r * (n & 1 ? a : 1) % P;
        a = 1l * a * a % P, n >>= 1;
      }
      return r;
    }
  }
  int iv6, n, m, sn, sm, ans;
  void main() {
    for (int i(1); i != P; ++i)
      if (6 * i % P == 1) { iv6 = i; break; }
    cin >> n >> m, cminmax(n, m);
    for (int i(1); i * i <= n; ++i)
      sn = (sn + n % i) % P;
    // cerr << __LINE__ << ' ' << sn << endl;
    for (int i(1); i * i < n; ++i) {
      int const l(max(i, n / (i + 1))), r(n / i);
      sn = (sn + 1l * n * (r - l)) % P;
      sn = (sn - 1l * (l + r + 1) * (r - l) / 2 % P * i) % P;
      // cerr << i << ' ' << l << ' ' << r << ' ' << sn << endl;
    }
    // cerr << __LINE__ << ' ' << sn << endl;
    for (int i(1); i * i <= m; ++i)
      sm = (sm + m % i) % P;
    // cerr << __LINE__ << ' ' << sm << endl;
    for (int i(1); i * i < m; ++i) {
      int const l(max(i, m / (i + 1))), r(m / i);
      sm = (sm + 1l * m * (r - l)) % P;
      sm = (sm - 1l * (l + r + 1) * (r - l) / 2 % P * i) % P;
      // cerr << i << ' ' << l << ' ' << r << ' ' << sm << endl;
    }
    // cerr << __LINE__ << ' ' << sm << endl;
    ans = 1l * sn * sm % P;
    // cerr << __LINE__ << ' ' << ans << endl;
    for (int l(1), r; l <= n; l = r + 1) {
      r = min(n / (n / l), m / (m / l)), --l;
      int const s0((r - l) % P);
      int const s1(1l * (l + r + 1) * (r - l) / 2 % P);
      int s2(0);
      s2 += 1l * r * (r + 1) % P * (2 * r + 1) % P * iv6 % P;
      s2 -= 1l * l * (l + 1) % P * (2 * l + 1) % P * iv6 % P;
      ans = (ans - 1l * n * m % P * s0) % P;
      ans = (ans + 1l * n / r * m % P * s1) % P;
      ans = (ans + 1l * m / r * n % P * s1) % P;
      ans = (ans - 1l * (n / r) * (m / r) % P * s2) % P;
      // cerr << l << ' ' << r << ' ' << ans << endl;
    }
    cout << (ans = (ans + P) % P) << endl;
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int t(1);
  // cin >> t;
  for (int i(1); i <= t; ++i) kh::main();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10
Accepted
time: 2ms
memory: 3684kb

input:

195 631


output:

13499636

result:

ok single line: '13499636'

Test #2:

score: 10
Accepted
time: 2ms
memory: 3732kb

input:

64 10872681


output:

1651075

result:

ok single line: '1651075'

Test #3:

score: 10
Accepted
time: 2ms
memory: 3604kb

input:

75 135111825


output:

1099449

result:

ok single line: '1099449'

Test #4:

score: 10
Accepted
time: 2ms
memory: 3668kb

input:

63 116177601


output:

17215072

result:

ok single line: '17215072'

Test #5:

score: 10
Accepted
time: 3ms
memory: 3596kb

input:

405041 602225


output:

4906861

result:

ok single line: '4906861'

Test #6:

score: 10
Accepted
time: 2ms
memory: 3668kb

input:

727429 937589


output:

4099574

result:

ok single line: '4099574'

Test #7:

score: 10
Accepted
time: 4ms
memory: 3612kb

input:

70337281 243937321


output:

16331489

result:

ok single line: '16331489'

Test #8:

score: 10
Accepted
time: 4ms
memory: 3672kb

input:

136349929 257383657


output:

19504124

result:

ok single line: '19504124'

Test #9:

score: 10
Accepted
time: 4ms
memory: 3668kb

input:

539154474 305587405


output:

8781805

result:

ok single line: '8781805'

Test #10:

score: 10
Accepted
time: 4ms
memory: 3680kb

input:

719865785 277727262


output:

937958

result:

ok single line: '937958'