b447: 【我愛Möbius】之最大公約數求和
Tags : 數論基礎
Accepted rate : 14人/21人 ( 67% ) [非即時]
評分方式:
Tolerant

最近更新 : 2015-07-28 02:15

Content
在做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$的最大公約數。

Input

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

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

Output
對於每筆測資,輸出求和結果。
Sample Input #1
2
3 4
10000000 10000000
Sample Output #1
16
1004297420038032
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 10.0s , <1M
Hint :
這是【我愛Möbius】系列的第三題,上一題是【我愛Möbius】之我愛Fibonacci,下一題是【我愛Möbius】之Fibonacci之夢
Tags:
數論基礎
出處:
[管理者:
liouzhou_101 (王启圣)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」