Description

对以下式子求值:

\[\sum_{i=1}^{n} \sum_{j=1}^{m} (n \bmod i) \cdot (m \bmod j)\]

Input

第一行两个整数 \(n, m\).

Output

一个整数表示答案 \(\bmod 19940417\) 的值.

Sample Input

3 4

Sample Output

1

Data Range

对于 100% 的数据 n, m<=10^9.

Explanation

\[\begin{aligned} &\sum_{i=1}^{n} \sum_{j=1 \land i \neq j}^{m}(n \bmod i)(m \bmod j)\\ = &\sum_{i=1}^{n} \sum_{j=1}^{m} (n - {\left \lfloor \frac{n}{i} \right \rfloor} i) (m - {\left \lfloor \frac{m}{j} \right \rfloor} j) - \sum_{i=1}^{min(n,m)} (n - {\left \lfloor \frac{n}{i} \right \rfloor} i) (m - {\left \lfloor \frac{m}{i} \right \rfloor} i)\\ = &\sum_{i=1}^{n} \sum_{j=1}^{m} (n - {\left \lfloor \frac{n}{i} \right \rfloor} i) (m - {\left \lfloor \frac{m}{j} \right \rfloor} j) - \sum_{i=1}^{min(n,m)} (n m + {\left \lfloor \frac{n}{i} \right \rfloor} {\left \lfloor \frac{m}{i} \right \rfloor} i^2 - (m {\left \lfloor \frac{n}{i} \right \rfloor} + n {\left \lfloor \frac{m}{i} \right \rfloor}) i) \end{aligned}\]

然后推完接着开始分块......

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const lli modr = 19940417;
const lli inv = 3323403;

lli sum(lli a, lli b) {
    return (b-a+1) * (a+b) / 2 % modr;
}
lli sum(lli x) {
    return x*(x+1) % modr * (2*x+1) % modr * inv % modr;
}
lli calc(lli n) {
    lli tmp = 0;
    for (lli i = 1, j; i <= n; i = j + 1) {
        j = n / (n / i);
        tmp = (tmp + n*(j-i+1) % modr - sum(i,j) * (n/i)) % modr;
    }
    return (tmp + modr) % modr;
}

lli n, m;
lli res = 0;

int main(int argc, char** argv)
{
    scanf("%lld%lld", &n, &m);
    res = calc(n) * calc(m) % modr;
    // Maintain relations
    if (n > m) swap(n, m);
    for (lli i = 1, j; i <= n; i = j + 1) {
        j = min(n/(n/i), m/(m/i));
        lli t1 = n * m % modr * (j-i+1) % modr,
            t2 = (n/i) * (m/i) % modr * (sum(j)-sum(i-1)+modr) % modr,
            t3 = (n/i*m + m/i*n) % modr * sum(i,j) % modr;
        res = (res - (t1 + t2 - t3) % modr + modr) % modr;
    }
    printf("%lld\n", res);
    return 0;
}