QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#486991 | #3681. 模积和 | KiharaTouma | 100 ✓ | 3ms | 3944kb | C++23 | 1.1kb | 2024-07-22 14:52:45 | 2024-07-22 14:52:50 |
Judging History
answer
//qoj3681
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll P = 19940417, i2 = 9970209, i6 = 3323403;
ll n, m;
ll sm(ll x){
x %= P;
return x * (x+1) % P * i2 % P;
}
ll sm(ll l, ll r){
return (sm(r) - sm(l-1) + P) % P;
}
ll pw(ll x){
x %= P;
return x * (x+1) % P * (x+x+1) % P * i6 % P;
}
ll pw(ll l, ll r){
return (pw(r) - pw(l-1) + P) % P;
}
ll clc(ll x){
ll ans = 0;
for(ll l = 1, r; l <= x; l = r + 1){
r = x / (x / l);
ans = (ans + (x / l) % P * sm(l, r)) % P;
}
return ans;
}
ll calc(ll x, ll y){
ll ans = 0;
for(ll l = 1, r; l <= min(x, y); l = r + 1){
r = min(x / (x / l), y / (y / l));
ans += x * y % P * (r-l+1) % P;
ans -= y * (x / l) % P * sm(l, r) % P;
ans -= x * (y / l) % P * sm(l, r) % P;
ans += (x / l) * (y / l) % P * pw(l, r) % P;
ans = (ans % P + P) % P;
}
return ans;
}
int main(){
scanf("%lld%lld", &n, &m);
ll ans = 0;
ans += (n * n % P + P - clc(n)) * (m * m % P + P - clc(m)) % P;
ans -= calc(n, m);
printf("%lld\n", (ans % P + P) % P);
return 0;
}
详细
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 0ms
memory: 3752kb
input:
195 631
output:
13499636
result:
ok single line: '13499636'
Test #2:
score: 10
Accepted
time: 0ms
memory: 3808kb
input:
64 10872681
output:
1651075
result:
ok single line: '1651075'
Test #3:
score: 10
Accepted
time: 1ms
memory: 3944kb
input:
75 135111825
output:
1099449
result:
ok single line: '1099449'
Test #4:
score: 10
Accepted
time: 1ms
memory: 3808kb
input:
63 116177601
output:
17215072
result:
ok single line: '17215072'
Test #5:
score: 10
Accepted
time: 0ms
memory: 3808kb
input:
405041 602225
output:
4906861
result:
ok single line: '4906861'
Test #6:
score: 10
Accepted
time: 0ms
memory: 3944kb
input:
727429 937589
output:
4099574
result:
ok single line: '4099574'
Test #7:
score: 10
Accepted
time: 0ms
memory: 3788kb
input:
70337281 243937321
output:
16331489
result:
ok single line: '16331489'
Test #8:
score: 10
Accepted
time: 2ms
memory: 3868kb
input:
136349929 257383657
output:
19504124
result:
ok single line: '19504124'
Test #9:
score: 10
Accepted
time: 3ms
memory: 3808kb
input:
539154474 305587405
output:
8781805
result:
ok single line: '8781805'
Test #10:
score: 10
Accepted
time: 3ms
memory: 3788kb
input:
719865785 277727262
output:
937958
result:
ok single line: '937958'