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
公開測資點#0 (100%): 10.0s , <1M

提示：

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

標籤:

數論基礎

出處:

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

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