QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#209105 | #3681. 模积和 | KHIN | 20 | 4ms | 3728kb | C++17 | 5.2kb | 2023-10-10 10:06:44 | 2023-10-10 10:06:44 |
Judging History
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'