题意

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

分析

以下均设\(n \le m\)

$$ \begin{align} & \sum_{i=1}^{n} \sum_{j=1}^{m} (n \ mod \ i)(m \ mod \ j)[i \neq 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) \right) \ mod \ 19940417 \\ \equiv & \left( \left( \sum_{i=1}^{n} (n \ mod \ i) \right) \left( \sum_{j=1}^{m} (m \ mod \ i) \right) - \sum_{i=1}^{n} (n \ mod \ i \cdot m \ mod \ i) \right) \ mod \ 19940417 \\ \end{align} $$

于是我们只需要快速求出\(\sum_{i=1}^{n} ( n \ mod \ i)\)和\(\sum_{i=1}^{n} ( n \ mod \ i \cdot m \ mod \ i )\)就能解决问题了。

$$ \begin{align} & \sum_{i=1}^{n} ( n \ mod \ i) \\ = & \sum_{i=1}^{n} \left( n - i \left \lfloor \frac{n}{i} \right \rfloor \right) \\ = & n^2 - \sum_{i=1}^{n} i \left \lfloor \frac{n}{i} \right \rfloor \\ & \sum_{i=1}^{n} ( n \ mod \ i \cdot \ m \ mod \ i) \\ = & \sum_{i=1}^{n} \left( n - i \left \lfloor \frac{n}{i} \right \rfloor \right) \left( m - i \left \lfloor \frac{m}{i} \right \rfloor \right) \\ = & n^2m + \sum_{i=1}^{n} i^2 \left \lfloor \frac{n}{i} \right \rfloor \left \lfloor \frac{m}{i} \right \rfloor - n\sum_{i=1}^{n} i \left \lfloor \frac{m}{i} \right \rfloor - m\sum_{i=1}^{n} i \left \lfloor \frac{n}{i} \right \rfloor \\ \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\n", (cal(n, n)*cal(m, m)%mo-cal(n, (ll)n*m)+mo)%mo);    return 0;}