QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#209105#3681. 模积和KHIN20 4ms3728kbC++175.2kb2023-10-10 10:06:442023-10-10 10:06:44

Judging History

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

  • [2023-10-10 10:06:44]
  • 评测
  • 测评结果:20
  • 用时:4ms
  • 内存:3728kb
  • [2023-10-10 10:06:44]
  • 提交

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;
    for (int i(1); i * i < n; ++i) {
      int const l(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;
    }
    for (int i(1); i * i <= m; ++i)
      sm = (sm + m % i) % P;
    for (int i(1); i * i < m; ++i) {
      int const l(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;
    }
    ans = 1l * sn * sm % P;
    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;
    }
    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();
}

详细

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 3720kb

input:

195 631


output:

13539902

result:

wrong answer 1st lines differ - expected: '13499636', found: '13539902'

Test #2:

score: 0
Wrong Answer
time: 2ms
memory: 3728kb

input:

64 10872681


output:

3364171

result:

wrong answer 1st lines differ - expected: '1651075', found: '3364171'

Test #3:

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

input:

75 135111825


output:

1099449

result:

ok single line: '1099449'

Test #4:

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

input:

63 116177601


output:

17215072

result:

ok single line: '17215072'

Test #5:

score: 0
Wrong Answer
time: 2ms
memory: 3724kb

input:

405041 602225


output:

3255764

result:

wrong answer 1st lines differ - expected: '4906861', found: '3255764'

Test #6:

score: 0
Wrong Answer
time: 2ms
memory: 3660kb

input:

727429 937589


output:

6309540

result:

wrong answer 1st lines differ - expected: '4099574', found: '6309540'

Test #7:

score: 0
Wrong Answer
time: 4ms
memory: 3608kb

input:

70337281 243937321


output:

7312988

result:

wrong answer 1st lines differ - expected: '16331489', found: '7312988'

Test #8:

score: 0
Wrong Answer
time: 4ms
memory: 3688kb

input:

136349929 257383657


output:

677344

result:

wrong answer 1st lines differ - expected: '19504124', found: '677344'

Test #9:

score: 0
Wrong Answer
time: 4ms
memory: 3724kb

input:

539154474 305587405


output:

17661718

result:

wrong answer 1st lines differ - expected: '8781805', found: '17661718'

Test #10:

score: 0
Wrong Answer
time: 2ms
memory: 3600kb

input:

719865785 277727262


output:

11700757

result:

wrong answer 1st lines differ - expected: '937958', found: '11700757'