b440. 【我愛Möbius】之互質對 - 高中生程式解題系統

內容

給定$n$和$m$，請你統計有序對$(a,b)$的個數，其中$1\leq a\leq n,1\leq b\leq m$且$a$與$b$互質。

$a$與$b$互質的定義是：$a$與$b$的最大公約數等於$1$。

輸入說明

第一行是一個正整數$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

9
60792712854483

測資資訊：

記憶體限制： 512 MB

提示：

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

標籤:

數論基礎

出處:

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

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