QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#809924 | #3681. 模积和 | LaDeX | 100 ✓ | 3ms | 3700kb | C++17 | 968b | 2024-12-11 18:17:48 | 2024-12-11 18:17:59 |
Judging History
answer
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const LL MOD = 19940417;
const LL inv6 = 3323403;
const LL inv2 = 9970209;
LL n, m;
LL Calc1(LL x, LL y) {
LL ret = 0;
for (LL l = 1, r; l <= y; l = r + 1) {
r = min(y, x / (x / l));
ret = (ret + (x / l) * (l + r) % MOD * (r - l + 1) % MOD * inv2 % MOD) % MOD;
}
return ret;
}
LL f(LL x) { return x * (x + 1) % MOD * (x * 2 + 1) % MOD * inv6 % MOD; }
LL Calc2(LL x, LL y) {
LL ret = 0;
for (LL l = 1, r; l <= x && l <= y; l = r + 1) {
r = min(y / (y / l), x / (x / l));
ret = (ret + (x / l) * (y / l) % MOD * (f(r) - f(l - 1)) % MOD) % MOD;
}
return ret;
}
LL Calc(LL x) {
return x * x % MOD - Calc1(x, x);
}
int main() {
ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
if (n > m) swap(n, m);
LL Ans = Calc(n) * Calc(m) % MOD - n * n % MOD * m % MOD + m * Calc1(n, n)
+ n * Calc1(m, n) - Calc2(n, m);
Ans = (Ans + MOD) % MOD;
cout << Ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 0ms
memory: 3660kb
input:
195 631
output:
13499636
result:
ok single line: '13499636'
Test #2:
score: 10
Accepted
time: 0ms
memory: 3700kb
input:
64 10872681
output:
1651075
result:
ok single line: '1651075'
Test #3:
score: 10
Accepted
time: 1ms
memory: 3640kb
input:
75 135111825
output:
1099449
result:
ok single line: '1099449'
Test #4:
score: 10
Accepted
time: 1ms
memory: 3696kb
input:
63 116177601
output:
17215072
result:
ok single line: '17215072'
Test #5:
score: 10
Accepted
time: 1ms
memory: 3648kb
input:
405041 602225
output:
4906861
result:
ok single line: '4906861'
Test #6:
score: 10
Accepted
time: 1ms
memory: 3640kb
input:
727429 937589
output:
4099574
result:
ok single line: '4099574'
Test #7:
score: 10
Accepted
time: 2ms
memory: 3584kb
input:
70337281 243937321
output:
16331489
result:
ok single line: '16331489'
Test #8:
score: 10
Accepted
time: 2ms
memory: 3652kb
input:
136349929 257383657
output:
19504124
result:
ok single line: '19504124'
Test #9:
score: 10
Accepted
time: 3ms
memory: 3652kb
input:
539154474 305587405
output:
8781805
result:
ok single line: '8781805'
Test #10:
score: 10
Accepted
time: 3ms
memory: 3572kb
input:
719865785 277727262
output:
937958
result:
ok single line: '937958'