比赛 |
2025.1.18 |
评测结果 |
AAAAAAAAAA |
题目名称 |
模积和 |
最终得分 |
100 |
用户昵称 |
djyqjy |
运行时间 |
0.079 s |
代码语言 |
C++ |
内存使用 |
3.45 MiB |
提交时间 |
2025-01-18 09:06:16 |
显示代码纯文本
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
int f=1,num=0;
char c=getchar();
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
return num*f;
}
const int MOD=19940417,inv2=9970209,inv6=3323403;
int n,m;
int ans,t,k;
int f(int l,int r){return (r*(r+1)%MOD-l*(l-1)%MOD+MOD)%MOD*inv2%MOD;}
int g(int l,int r){return (r*(r+1)%MOD*(2*r+1)%MOD-l*(l-1)%MOD*(2*l-1)%MOD+MOD)%MOD*inv6%MOD;}
signed main()
{
freopen("modmuladd.in","r",stdin);
freopen("modmuladd.out","w",stdout);
n=read();m=read();if(n>m) swap(n,m);
for(int l=1,r;l<=m;l=r+1)
{
r=m/(m/l);
ans=(ans+f(l,r)*(m/l)%MOD)%MOD;
}
ans=(m*m%MOD-ans+MOD)%MOD;
for(int l=1,r;l<=n;l=r+1)
{
r=n/(n/l);
t=(t+f(l,r)*(n/l)%MOD)%MOD;
}
k=t;ans=((n*n%MOD-t+MOD)%MOD*ans%MOD-n*n%MOD*m%MOD+MOD)%MOD;
ans=(ans+m*t%MOD)%MOD;
t=0;
for(int l=1,r;l<=n;l=r+1)
{
r=min(n,m/(m/l));
t=(t+f(l,r)*(m/l)%MOD)%MOD;
}
ans=(ans+t*n%MOD)%MOD;
t=0;
for(int l=1,r;l<=n;l=r+1)
{
r=min(n/(n/l),m/(m/l));
t=(t+g(l,r)*(n/l)%MOD*(m/l)%MOD)%MOD;
}
ans=(ans-t+MOD)%MOD;
printf("%lld",ans);
return 0;
}