Bội số chung nhỏ nhất – Thanh Hóa 2024-2025

Đề bài

Bội số chung nhỏ nhất của 2 số nguyên dương x và y là số nguyên dương nhỏ nhất chia hết cho cả x và y, kí hiệu LCM(x,y).

Cho hai số nguyên dương a và b ( $a \le b$ ).

Yêu cầu: Hãy đếm số cặp số nguyên dương x, y sao cho LCM(x, y) bằng tích các số nguyên liên tiếp từ a đến b (trường hợp a bằng b thì tích này bằng a).

Dữ liệu vàoCAU4.INP

Đọc từ tệp CAU4.INP có cấu trúc như sau:

Dòng đầu ghi số nguyên dương $T$ ( $T \le 10$ ) là số test.
$T$ dòng tiếp theo, mỗi dòng là một test chứa hai số nguyên dương $a, b$ ( $1 \le a \le b \le 10^6$ ).

Kết quả raCAU4.OUT

Ghi ra tệp CAU4.OUT gồm T dòng, mỗi dòng là phần dư của kết quả tìm được khi chia cho $10^9 + 7$ .

Ràng buộc

Có 40% số điểm của bài có $a, b \le 10$ ;
Có 30% số điểm tiếp theo của bài có $a, b \le 100$ ;
Có 30% số điểm còn lại của bài không có ràng buộc gì thêm.

Ví dụ

Dữ liệu vàoCAU4.INP

2
3 4
7 7

Kết quả raCAU4.OUT

15
3

Giải thích

Test 1 có 15 cặp số thỏa mãn: (1,12); (2,12); (3, 4); (3,12); (4,3); (4,6); (4,12); (6,4); (6,12); (12,1); (12,2); (12,3); (12,4); (12,6); (12,12)
Test 2 có 3 cặp số thỏa mãn: (1, 7); (7, 1); (7, 7).