GCD 与 LCM - 問題

#4278. GCD 与 LCM

統計

AI Translation — This statement was translated using AI and may contain inaccuracies. Please refer to the original statement if in doubt.

bobo 擅长计算 GCD（最大公约数）和 LCM（最小公倍数）。但今天他被一道题目难住了：计算所有满足 $1 \le i \le n, 1 \le j \le m$ 且 $\gcd(i, j) \le a$ 的 $\text{lcm}(i, j)$ 之和，结果对 $(10^9 + 7)$ 取模。

输入格式

第一行包含一个整数 $q$，表示询问的次数 ($1 \le q \le 10^4$)。接下来的 $q$ 行，每行包含 3 个整数 $n, m, a$，含义如题所述 ($1 \le n, m, a \le 10^5$)。

输出格式

对于每个询问，输出一行，表示所求的和。

样例

样例输入 1

2
2 2 1
3 4 2

样例输出 1

5
45

Editorials

ID	Type	Status	Title	Posted By	Last Updated	Actions
#171	Editorial	Open	题解	jiangly	2025-12-12 23:48:26	View

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 1

ID	Type	Status	Title	Posted By	Last Updated	Actions
#816	General Discussion	Open	卡常相关	qoj_bot	2026-01-27 17:02:57	View

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
Do not submit duplicated issues.
Issues must be filed in English or Chinese only.

Active Issues 0

No issues in this category.

Closed/Resolved Issues 0