题目描述

给定 $t$ 组询问 $n,m,p,q$，求：

$$ \sum_{i=1}^{n}\sum_{j=1}^{m} \frac{\text{lcm}(i,j)^q}{\gcd(i,j)^ {p}} \cdot \phi (\gcd(i,j)) $$

输入格式

第一行两个数 $T$ 和 $op$，$op=1$ 表示有加密。

剩下如题。

输出格式

$T$ 行，每行形如 Case #1: Ans。

7 0
1 2 1 2
5 6 1 1
17 12 3 4
15 12 2 5
19 18 3 6
1111111 1111111 8 9
1111111 1111111 9 3

Case #1: 5
Case #2: 217
Case #3: 293971
Case #4: 48591
Case #5: 623165
Case #6: 1019165
Case #7: 1070010

数据范围与规模

本题的测试点共包含 $5$ 个基本数据范围:

• 对于 $20\%$ 的数据，$1 \le n,m \le 111$
• 对于 $40\%$ 的数据，$1 \le n,m \le 1111$
• 对于 $60\%$ 的数据，$1 \le n,m \le 11111$
• 对于 $80\%$ 的数据，$1 \le n,m \le 111111$
• 对于 $100\%$ 的数据，$1 \le n,m \le 1111111,t \le 10^ {3} ,0 \le p \le q \le 9$
• 对于每个基本数据范围, 均包含 $10$ 个测试点。数据保证, 对于同一个基本数据范围内的所有测试点, 加密与未加密的数据各占半。同时, 对于属于同一类型的 $5$ 个测试点, 保证数据中所有 $p$ 和 $q$ 的最大值依次为 $1,3,5,7,9$。