首页 > 代码库 > BZOJ 2956 模积和（分块）
BZOJ 2956 模积和（分块）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=2956
【题目大意】
求∑∑((n%i)*(m%j))其中1<=i<=n,1<=j<=m,i≠j。
【题解】
$∑_{i=1}^{n}∑_{j=1}^{m}((n\mod i)*(m\mod j))(i≠j)$
$=∑_{i=1}^{n}∑_{j=1}^{m}(n-\lfloor n/i\rfloor*i)*(m-\lfloor m/j\rfloor*j)-∑_{i=1}^{min(n,m)}(n-\lfloor n/i\rfloor*i)*(m-\lfloor m/i\rfloor*i)$
$=∑_{i=1}^{n}(n-\lfloor n/i\rfloor)*∑_{i=1}^{m}(m-\lfloor m/i\rfloor)$
$-∑_{i=1}^{min(n,m)}n*m-n*\lfloor m/i\rfloor*i-m*\lfloor n/i\rfloor*i+\lfloor n/i\rfloor\lfloor m/i\rfloor*i*i$
我们对于n/i分段统计即可。
【代码】
#include <cstdio>#include <algorithm>using namespace std;typedef long long LL;const LL inv6=3323403;const LL mod=19940417;LL n,m,ans;LL sum(LL a,LL b){return (b-a+1)*(a+b)/2%mod;}LL sum2(LL x){return x*(x+1)%mod*(2*x+1)%mod*inv6%mod;}LL cal(LL n){ LL res=0; for(LL l=1,r;l<=n;l=r+1){ r=n/(n/l); res=(res+n*(r-l+1)%mod-sum(l,r)*(n/l))%mod; }return (res+mod)%mod;}int main(){ while(~scanf("%lld%lld",&n,&m)){ ans=cal(n)*cal(m)%mod; if(n>m)swap(n,m); for(int l=1,r;l<=n;l=r+1){ r=min(n/(n/l),m/(m/l)); LL s1=n*m%mod*(r-l+1)%mod; LL s2=(n/l)*(m/l)%mod*(sum2(r)-sum2(l-1)+mod)%mod; LL s3=(n/l*m+m/l*n)%mod*sum(l,r)%mod; ans=(ans-(s1+s2-s3)%mod+mod)%mod; }printf("%lld\n",ans); }return 0;}
BZOJ 2956 模积和（分块）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。