QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#209112 | #3681. 模积和 | KHIN | 100 ✓ | 4ms | 3732kb | C++17 | 5.7kb | 2023-10-10 10:17:38 | 2023-10-10 10:17:38 |
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;
// 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();
}
詳細信息
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'