b447. 【我愛Möbius】之最大公約數求和

內容

在做NOI2010 Day1.1.能量采集的時候，只要稍微想一下，就會發現其實他是叫我們求最大公約數之和。但是那題題目敘述太長了，不如這題簡潔明了。

給定 $n$ 和 $m$ ，請你對所有有序對 $(a, b)$ ，其中 $1 \leq a \leq n, 1 \leq b \leq m$ ，求 $\gcd (a, b)$ 之和，即

$\sum_{i = 1}^{n} \sum_{j = 1}^{m} \gcd (i, j)$

其中，

\gcd (a, b)

表示

a

和

b

的最大公約數。

輸入說明

第一行是一個正整數 $T (1 \leq T \leq 10^{4})$ ，代表測資筆數。

接下來 $T$ 行，每行兩個正整數 $n (1 \leq n \leq 10^{7})$ 和 $m (1 \leq m \leq 10^{7})$ 。

輸出說明

對於每筆測資，輸出求和結果。

範例輸入 #1

2
3 4
10000000 10000000

範例輸出 #1

16
1004297420038032

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (100%): 10.0s , <1M

提示：

這是【我愛Möbius】系列的第三題，上一題是【我愛Möbius】之我愛Fibonacci，下一題是【我愛Möbius】之Fibonacci之夢。

標籤:

數論基礎

出處:

[管理者： liouzhou_101 (王启圣) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」