终于会用$\LaTeX$和Typora啦

$$

\sum_{i=1}^{n}\sum_{j=1}^{m}(n\%i)(m\%j)

$$

即

$$

\begin{align}

&\sum_{i=1}^{n}n\%i\sum_{j=1}^{m}m\%j\\

&=\sum_{i=1}^{n}(n-\lfloor n/i \rfloor *i)\sum_{j=1}^{m}(m-\lfloor m/j \rfloor *j)

\end{align}

$$

又有i$\neq$j

所以还要求

$$

\begin{align}

\sum_{i=1}^{min(n,m)}(n-\lfloor n/i \rfloor *i)(m-\lfloor m/i \rfloor *i)

\end{align}

$$

展开求，加的项可以直接等差和分块求

涉及$i^2$的项可以用平方求和公式：

$$

\sum_{i=1}^{n}i^{2}=\frac{n(n+1)(2n+1)}{6}

$$

由于本题模数不是质数，不可以用费马小定理解逆元，要先用exgcd或欧拉定理解出inv6

宁可多$\% $也不要少$\% $

 

#include
     
      using namespace std;const int p=19940417;const int inv6=3323403;typedef long long ll;int n,m;ll ans1,ans2,ans3,ans;ll qsum(ll n){    return ((n*(n+1))%p*(2*n+1)%p*inv6)%p;}int main(){    cin>>n>>m;    ans1=(ll)n%p*n%p;    ans2=(ll)m%p*m%p;    for(int i=1;i<=n;i++){        int t=n/i,j=n/t;        ans1-=((ll)(i+j)*(j-i+1)/2%p)*t;            i=j;        ans1%=p;    }    for(int i=1;i<=m;i++){        int t=m/i,j=m/t;        ans2-=((ll)(i+j)*(j-i+1)/2%p)*t;        i=j;        ans2%=p;        }    ans3=((ll)min(n,m)*n%p)*m;    for(int i=1;i<=min(n,m);i++){        int t1=n/i;        int t2=m/i;        int j=min(n/t1,m/t2);        ans3-=((ll)(i+j)*(j-i+1)/2*t1%p)*m%p;        ans3-=((ll)(i+j)*(j-i+1)/2*t2%p)*n%p;        ans3+=((ll)(qsum(j)-qsum(i-1))*t1%p)*t2;        i=j;        ans3=(ans3%p+p)%p;    }    ans=(ans1*ans2%p-ans3+p)%p;    cout<
      
       <