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

內容

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

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

\[\sum_{i=1}^n \sum_{j=1}^m \mathrm{gcd}(i,j)\]

其中，$\mathrm{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 (王启圣) ]

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