c819: gcd(Fm, Fn) 之求和問題
Tags :
Accepted rate : 2人/9人 ( 22% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-06-09 23:03

Content

定義費氏數列 $\color{black}{F_1 = F_2 = 1,\ F_n = F_{n-2} + F_{n-1}\ \forall\ n > 2}$。

給定 $\color{black}{n,\ m}$ ,你能求出 $\color{black}{\operatorname{gcd}(F_m, F_n)}$ 的值嗎?

現在有個更加複雜的問題,請你對所有有序對 $\color{black}{(a,\ b)}$,其中 $\color{black}{1 \le a \le n,\ 1 \le b \le m}$ ,求 $\color{black}{\operatorname{gcd}(F_a,\ F_b)}$ 之和,即

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

Input

第一行是兩個正整數 $\color{black}{C (1 \le C \le 10^7),\ T (1 \le T \le 10^4)}$,代表 $\color{black}{n,\ m}$ 的上限和測資筆數。

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

Output

對於每筆測資,輸出求和結果,請對 1000000007 取模再輸出。

Sample Input
1000 2
3 4
1000 1000
Sample Output
13
542559755
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (33%): 4.0s , <1M
公開 測資點#1 (33%): 10.0s , <1M
公開 測資點#2 (34%): 10.0s , <1M
Hint :

Small: $\color{black}{C \le 10^3}$, Time Limit = 4s

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

Tags:
出處:
[管理者:
icube (輸光光)
]


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