GCD vs LCM

시간 제한2.5초메모리 제한512 MB

요약

n, m, a가 1e5 이하인 q개의 질의마다 i<=n, j<=m이고 gcd(i,j)<=a인 모든 쌍의 lcm(i,j) 합을 1e9+7로 나눈 나머지를 구한다.

문제

bobo는 GCD(최대공약수)와 LCM(최소공배수)을 잘 다룬다.

그런데 오늘 그는 $1 \leq i \leq n$ , $1 \leq j \leq m$ 이고 $\gcd(i, j) \leq a$ 인 모든 순서쌍에 대해 $\mathrm{lcm}(i, j)$ 의 합을 $(10^9 + 7)$ 로 나눈 나머지를 구하는 문제에 막혔다.

첫째 줄에 질문의 개수 $q$ 가 주어진다 ( $1 \leq q \leq 10^4$ ).

다음 $q$ 개의 줄에는 각각 문제에서 설명한 대로 정수 $n, m, a$ 가 주어진다 ( $1 \leq n, m, a \leq 10^5$ ).

각 질문마다 합을 나타내는 정수를 한 줄에 하나씩 출력한다.