题意

求(sum_{i=1}^{n} sum_{j=1}^{m} (n mod i)(m mod j)[i eq j] mod 19940417), ((n, m le 10^9))

分析

以下均设(n le m) $$ egin{align} & sum_{i=1}^{n} sum_{j=1}^{m} (n mod i)(m mod j)[i eq j] mod 19940417 \ equiv & left( sum_{i=1}^{n} sum_{j=1}^{m} (n mod i)(m mod j) - sum_{i=1}^{n} (n mod i cdot m mod i) ight) mod 19940417 \ equiv & left( left( sum_{i=1}^{n} (n mod i) ight) left( sum_{j=1}^{m} (m mod i) ight) - sum_{i=1}^{n} (n mod i cdot m mod i) ight) mod 19940417 \ end{align} $$ 于是我们只需要快速求出(sum_{i=1}^{n} ( n mod i))和(sum_{i=1}^{n} ( n mod i cdot m mod i ))就能解决问题了。 $$ egin{align} & sum_{i=1}^{n} ( n mod i) \ = & sum_{i=1}^{n} left( n - i left lfloor frac{n}{i} ight floor ight) \ = & n^2 - sum_{i=1}^{n} i left lfloor frac{n}{i} ight floor \ & sum_{i=1}^{n} ( n mod i cdot m mod i) \ = & sum_{i=1}^{n} left( n - i left lfloor frac{n}{i} ight floor ight) left( m - i left lfloor frac{m}{i} ight floor ight) \ = & n^2m + sum_{i=1}^{n} i^2 left lfloor frac{n}{i} ight floor left lfloor frac{m}{i} ight floor - nsum_{i=1}^{n} i left lfloor frac{m}{i} ight floor - msum_{i=1}^{n} i left lfloor frac{n}{i} ight floor \ end{align} $$

题解

于是分块大法好... #include using namespace std; typedef long long ll; const int mo=19940417; ll cal(int n, ll a) { ll ret=a%mo*n%mo, tp=0; for(int i=1, pos=0; i<=n; i=pos+1) { pos=n/(n/i); tp+=(a/i)%mo*(((ll)(pos+1)*pos/2-(ll)(i-1)*i/2)%mo)%mo; if(tp>=mo) { tp-=mo; } } return (ret-tp+mo)%mo; } int main() { int n, m; scanf("%d%d", &n, &m); if(n>m) { swap(n, m); } printf("%lld ", (cal(n, n)*cal(m, m)%mo-cal(n, (ll)n*m)+mo)%mo); return 0; }