比赛 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;
}