Cho dãy số nguyên gồm n phần tử a1,a2,...,an với ai(1≤i≤n) thuộc tập hợp {1,2,3,...,K}
Như vậy, tức là có KN dãy như vậy.
Yêu cầu: Tính tổng của tất cả gcd(a1,a2,...,an) của KN dãy trên.
Ghi chú: gcd(x,y) tức là ước chung lớn nhất của hai số x,y
Input:
Dòng thứ nhất chứa số t(1≤t≤10) - Thể hiện số testcase
t dòng tiếp theo,ứng với mỗi dòng, gồm 2 số nguyên N,K(2≤N≤105,1≤K≤105)
Output:
Ứng với mỗi testcase, in ra đáp án cần tìm mod 109+7
Ví dụ:
Input:
1
2 2
Output:
5
Giải thích: gcd(1,1)+gcd(1,2)+gcd(2,1)+gcd(2,2)=1+1+1+2=5
lqdoj -> Tổng GCD :))
Loga
Sinh Học lớp 12
