e254: 公因數求和
Tags : 數論基礎
Accepted rate : 2人/3人 ( 67% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-06-09 18:50

Content

b447 裡,要求的是所有有序對 $\color{black}{(a,\ b)}$ 的最大公因數之和,如果去掉「最大」改為求所有公因數之和,當然也有良好的解法。
給定 $\color{black}{n}$ 和 $\color{black}{m}$ ,請你對所有有序對 $\color{black}{(a,\ b)}$,其中 $\color{black}{1 \le a \le n,\ 1 \le b \le m}$ ,求 $\color{black}{\sigma (\operatorname{gcd}(a,\ b))}$ 之和,即

$\color{black}{\displaystyle \sum_{i=1}^n \sum_{j=1}^m \sigma (\operatorname{gcd}(i,\ j))}$

其中,$\color{black}{\operatorname{gcd}(a,\ b)}$ 表示 $\color{black}{a}$ 和 $\color{black}{b}$ 的最大公因數,$\color{black}{\sigma(a)}$ 表示 $\color{black}{a}$ 的正因數之和。

Input

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

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

Output

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

Sample Input
2
3 4
10000000 10000000
Sample Output
19
1595007865125414
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (33%): 2.0s , <1M
公開 測資點#1 (33%): 5.0s , <1M
公開 測資點#2 (34%): 5.0s , <1M
Hint :

Small: $\color{black}{n,\ m \le 10^3}$, Time Limit = 2s

Large: $\color{black}{n,\ m \le 10^7}$, Time Limit = 5s

可能沒有看起來那麼難。

Tags:
數論基礎
出處:
[管理者:
icube (輸光光)
]


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