QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#799055 | #3681. 模积和 | Kevin911 | 100 ✓ | 6ms | 3800kb | C++20 | 930b | 2024-12-04 21:13:15 | 2024-12-04 21:13:16 |
Judging History
answer
#include<bits/stdc++.h>
#define int __int128
using namespace std;
const int mod=19940417;
int n,m,s1,s2,s3;
int read()
{
int x=0;
char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9')
{
x=(x<<3)+(x<<1)+(c&15);
c=getchar();
}
return x;
}
void print(int x)
{
if(x>9) print(x/10);
putchar(x%10+'0');
}
signed main()
{
n=read(),m=read();
for(int l=1,r=0;l<=n;l=r+1)
{
r=n/(n/l);
s1=(s1+(r-l+1)*n%mod-(n/l)*((l+r)*(r-l+1)/2%mod)%mod+mod)%mod;
}
for(int l=1,r=0;l<=m;l=r+1)
{
r=m/(m/l);
s2=(s2+(r-l+1)*m%mod-(m/l)*((l+r)*(r-l+1)/2%mod)%mod+mod)%mod;
}
for(int l=1,r=0;l<=min(n,m);l=r+1)
{
r=min(n/(n/l),m/(m/l));
s3=(s3+(r-l+1)*n%mod*m%mod-n*(m/l)%mod*((l+r)*(r-l+1)/2%mod)%mod-m*(n/l)%mod*((l+r)*(r-l+1)/2%mod)%mod+(n/l)*(m/l)%mod*((r*(r+1)*(r*2+1)/6%mod)%mod-(l*(l-1)*(l*2-1)/6%mod)+mod)%mod+mod*2)%mod;
}
print((s1*s2%mod-s3+mod)%mod);
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 0ms
memory: 3800kb
input:
195 631
output:
13499636
result:
ok single line: '13499636'
Test #2:
score: 10
Accepted
time: 0ms
memory: 3576kb
input:
64 10872681
output:
1651075
result:
ok single line: '1651075'
Test #3:
score: 10
Accepted
time: 1ms
memory: 3628kb
input:
75 135111825
output:
1099449
result:
ok single line: '1099449'
Test #4:
score: 10
Accepted
time: 1ms
memory: 3620kb
input:
63 116177601
output:
17215072
result:
ok single line: '17215072'
Test #5:
score: 10
Accepted
time: 1ms
memory: 3560kb
input:
405041 602225
output:
4906861
result:
ok single line: '4906861'
Test #6:
score: 10
Accepted
time: 1ms
memory: 3628kb
input:
727429 937589
output:
4099574
result:
ok single line: '4099574'
Test #7:
score: 10
Accepted
time: 4ms
memory: 3516kb
input:
70337281 243937321
output:
16331489
result:
ok single line: '16331489'
Test #8:
score: 10
Accepted
time: 4ms
memory: 3624kb
input:
136349929 257383657
output:
19504124
result:
ok single line: '19504124'
Test #9:
score: 10
Accepted
time: 6ms
memory: 3628kb
input:
539154474 305587405
output:
8781805
result:
ok single line: '8781805'
Test #10:
score: 10
Accepted
time: 6ms
memory: 3624kb
input:
719865785 277727262
output:
937958
result:
ok single line: '937958'