?

【題目鏈接】?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 \frac{n}{i}\rfloor*i)*(m-\lfloor \frac{m}{j}\rfloor*j)-∑_{i=1}^{min(n,m)}(n-\lfloor \frac{n}{i}\rfloor*i)*(m-\lfloor \frac{m}{i}\rfloor*i)$
　　$=∑_{i=1}^{n}(n-\lfloor \frac{n}{i}\rfloor)*∑_{i=1}^{m}(m-\lfloor \frac{m}{i}\rfloor)$
　　$-∑_{i=1}^{min(n,m)}n*m-n*\lfloor \frac{m}{i}\rfloor*i-m*\lfloor \frac{n}{i}\rfloor*i+\lfloor \frac{n}{i}\rfloor\lfloor \frac{m}{i}\rfloor*i^2$

　　我們對于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; }

　　

轉載于:https://www.cnblogs.com/forever97/p/bzoj2956.html

總結

以上是生活随笔為你收集整理的BZOJ 2956 模积和（分块）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。