QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#799050 | #3681. 模积和 | Kevin911 | 60 | 7ms | 3864kb | C++20 | 1.0kb | 2024-12-04 21:10:31 | 2024-12-04 21:10:32 |
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');
}
int po(int x,int y)
{
int res=1ll,r=x;
for(int i=y;i;i>>=1)
{
if(i&1) res=res*r%mod;
r=r*r%mod;
}
return res;
}
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%mod+1)/6%mod)%mod-(l*(l-1)*(l*2%mod-1)/6%mod)+mod)%mod+mod*3)%mod;
}
print((s1*s2%mod-s3+mod)%mod);
}
详细
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 0ms
memory: 3556kb
input:
195 631
output:
13499636
result:
ok single line: '13499636'
Test #2:
score: 10
Accepted
time: 1ms
memory: 3828kb
input:
64 10872681
output:
1651075
result:
ok single line: '1651075'
Test #3:
score: 10
Accepted
time: 1ms
memory: 3788kb
input:
75 135111825
output:
1099449
result:
ok single line: '1099449'
Test #4:
score: 10
Accepted
time: 1ms
memory: 3864kb
input:
63 116177601
output:
17215072
result:
ok single line: '17215072'
Test #5:
score: 10
Accepted
time: 0ms
memory: 3564kb
input:
405041 602225
output:
4906861
result:
ok single line: '4906861'
Test #6:
score: 10
Accepted
time: 1ms
memory: 3636kb
input:
727429 937589
output:
4099574
result:
ok single line: '4099574'
Test #7:
score: 0
Wrong Answer
time: 4ms
memory: 3620kb
input:
70337281 243937321
output:
3037903
result:
wrong answer 1st lines differ - expected: '16331489', found: '3037903'
Test #8:
score: 0
Wrong Answer
time: 4ms
memory: 3824kb
input:
136349929 257383657
output:
12857344
result:
wrong answer 1st lines differ - expected: '19504124', found: '12857344'
Test #9:
score: 0
Wrong Answer
time: 6ms
memory: 3852kb
input:
539154474 305587405
output:
2135211
result:
wrong answer 1st lines differ - expected: '8781805', found: '2135211'
Test #10:
score: 0
Wrong Answer
time: 7ms
memory: 3564kb
input:
719865785 277727262
output:
7584990
result:
wrong answer 1st lines differ - expected: '937958', found: '7584990'