比赛 |
SYOI 专题 4:分块(根号杂烩) |
评测结果 |
AAAAAAAAAA |
题目名称 |
模积和 |
最终得分 |
100 |
用户昵称 |
op_组撒头屯 |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2024-04-17 17:28:04 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=19940417;
const ll inv2=9970209;
const ll inv6=3323403;
ll n,m,ans=0;
ll sum(ll l,ll r){
return (l+r)*(r-l+1)%mod*inv2%mod;
}
ll sum2(ll l,ll r){
return (r*(r+1)%mod*(2*r+1)%mod*inv6%mod-l*(l-1)%mod*(2*l-1)%mod*inv6%mod+mod)%mod;
}
int main(){
freopen ("modmuladd.in","r",stdin);
freopen ("modmuladd.out","w",stdout);
scanf("%lld%lld",&n,&m);
if (n>m)swap(n,m);
ll tmp1=n*n%mod,tmp2=m*m%mod,tmp3=n*n%mod*m%mod;
for (ll l=1,r;l<=n;l=r+1){
r=n/(n/l);tmp1=(tmp1-sum(l,r)*(n/l)%mod+mod)%mod;
}
for (ll l=1,r;l<=m;l=r+1){
r=m/(m/l);tmp2=(tmp2-sum(l,r)*(m/l)%mod+mod)%mod;
}
for (ll l=1,r;l<=n;l=r+1){
r=min(n/(n/l),m/(m/l));
tmp3=(tmp3-sum(l,r)*((n/l)*m%mod+(m/l)*n%mod)%mod+sum2(l,r)*(n/l)%mod*(m/l)%mod+mod)%mod;
}
printf("%lld\n",(tmp1*tmp2%mod-tmp3+mod)%mod);
return 0;
}