P2260 [清华集训 2012] 模积和 - Description
给定正整数 \(n\) 和 \(m\)，求
\[\sum_{i=1}^{n} \sum_{j=1}^{m} (n \bmod i) \times (m \bmod j), i \neq j\mod 19940417
\]
的值
\(1\le n,m\le 10^9\)。
P2260 [清华集训 2012] 模积和 - Solution
感觉有点无脑。
首先令 \(n\le m\)。
\[\begin{aligned}
ans&=\sum_{i=1}^n\sum_{j=1}^m (n\bmod i) \times (m\bmod j)-\sum_{i=1}^n (n\bmod i)\times (m\bmod i)\\&=
\sum_{i=1}^n \left ( n\bmod i \right )\times \sum_{i=1}^m \left ( m\bmod i\right )-\sum_{i=1}^n \left ( n\bmod i \right )\times \left ( m\bmod i \right )\\&=
\sum_{i=1}^n \left ( n- \lfloor \frac{n}{i} \rfloor \times i \right )\times \sum_{i=1}^m \left ( m-\lfloor \frac{m}{i} \rfloor \times i \right )-\sum_{i=1}^n \left ( n-\lfloor \frac{n}{i} \rfloor \times i \right )\times \left ( m-\lfloor \frac{m}{i} \rfloor \times i \right )
\\&=
\left ( n^2-\sum_{i=1}^n \lfloor \frac{n}{i} \rfloor \times i \right )\times \left ( m^2-\sum_{i=1}^m \lfloor \frac{m}{i} \rfloor \times i \right )-\sum_{i=1}^n \left ( n\times m-n\times \lfloor \frac{m}{i} \rfloor\times i - m\times \lfloor \frac{n}{i} \rfloor\times i + \lfloor \frac{n}{i} \rfloor \times \lfloor \frac{m}{i} \rfloor \times i^2 \right )\\&=\left ( n^2-\sum_{i=1}^n \lfloor \frac{n}{i} \rfloor \times i \right )\times \left ( m^2-\sum_{i=1}^m \lfloor \frac{m}{i} \rfloor \times i \right )-n^2m+n\times \sum_{i=1}^n \lfloor \frac{m}{i} \rfloor \times i+m\times \sum_{i=1}^n \lfloor \frac{n}{i} \rfloor \times i -\sum_{i=1}^n \lfloor \frac{n}{i} \rfloor \lfloor \frac{m}{i} \rfloor i^2
\end{aligned}
\]
现在这坨东西是 \(O(n)\) 的。碰到下取整那当然是 imagine 一下数论分块啦
形如 \(\sum \lfloor x\rfloor \times k\) 是经典的，这里主要讲讲最后面那一坨，即
\[\sum_{i=1}^n \lfloor \frac{n}{i} \rfloor \times \lfloor \frac{m}{i} \rfloor \times i^2
\]
这个东西我们称之为 二维数论分块。类似一维地，存在类似的规律，即在一个块内 \(\lfloor \frac{n}{i} \rfloor \times \lfloor \frac{m}{i} \rfloor\) 相等。
此处为了使两个下取整的积相等，更新右端点时应比较两个下取整，看哪个离左端点距离近。
时间复杂度还是 \(O(\sqrt{n})\)。
这题还有个难点是 \(O(1)\) 算 \(\sum i^2\)，但是这是个小学数学题，只挂个结论。
\[\sum_{i=1}^n i^2=\frac{n(n+1)(2n+1)}{6}
\]
#include<bits/stdc++.h>
#define int long long
#define mod 19940417
using namespace std;
long long n,m,ans,ans1,sumn,summ,sumnm,qwqq;
inline void init_n(){int r=1;for(int l=1;l<=n;l=r+1){int now=n/l;r=n/now;sumn+=(l+r)*(r-l+1)/2%mod*now%mod;sumn%=mod;}return;
}
inline void init_m(){int r=1;for(int l=1;l<=m;l=r+1){int now=m/l;r=m/now;summ+=(l+r)*(r-l+1)/2%mod*now%mod;summ%=mod;}return;
}
int S(int n){return 1ll*n*(n+1)%mod*(n+n+1)%mod*3323403%mod;}
inline void get_sumnm(){int r=1;for(int l=1;l<=m;l=r+1){int now=m/l;r=m/now;if(r>=n){sumnm+=(l+n)*(n-l+1)/2%mod*now%mod;break;}sumnm+=(l+r)*(r-l+1)/2%mod*now%mod;sumnm%=mod;}return;
}
inline void qwq(){int r=1;for(int l=1;l<=n;l=r+1){int now=m/l;r=min(n/(n/l),m/(m/l));qwqq+=(n/l)*now%mod*(S(r)-S(l-1))%mod;qwqq%=mod;}return;
}
signed main(){cin>>n>>m;if(n>m){swap(n,m);}init_n();init_m();get_sumnm();qwq();ans=n*n%mod;ans-=sumn;ans=(ans%mod+mod)%mod;ans1=m*m%mod;ans1-=summ;ans1=(ans1%mod+mod)%mod;ans*=ans1;ans%=mod;ans-=n*n%mod*m%mod;ans=(ans%mod+mod)%mod;ans+=n%mod*sumnm%mod;ans%=mod;ans+=m*sumn%mod;ans%=mod;ans-=qwqq;ans=(ans%mod+mod)%mod;cout<<ans<<endl;return 0;
}