QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100

# 3681. 模积和

Statistics

问题描述

求 $\sum\limits_{i=1}^n \sum\limits_{j=1}^m [i \ne j] (n \bmod i) (m \bmod j)$

输入格式

第一行两个数 $n,m$。

输出格式

一个整数表示答案 $\bmod 19\,940\,417$ 的值

样例输入

3 4

样例输出

1

样例说明

答案为 $\begin{split}(3 \bmod 1)\times(4 \bmod 2)+(3 \bmod 1) \times (4 \bmod 3)+(3 \bmod 1) \times (4 \bmod 4) + (3 \bmod 2) \times (4 \bmod 1) + (3 \bmod 2) \times (4 \bmod 3) +\\ (3 \bmod 2) \times (4 \bmod 4) + (3 \bmod 3) \times (4 \bmod 1) + (3 \bmod 3) \times (4 \bmod 2) + (3 \bmod 3) \times (4 \bmod 4) = 1\end{split}$

数据规模和约定

对于 $10\%$ 的数据 $n,m\leq 1\,000$;

对于 $30\%$ 的数据 $n,m \leq 1\,000\,000$;

另有 $30\%$ 的数据 $n \leq 100$,$m \leq 10^9$;

对于 $100\%$ 的数据 $n,m \leq 10^9$。