#3309. DZY Loves Math

DZY Loves Math

题目描述

对于正整数 nn,定义 f(n)f(n)nn 所含质因子的最大幂指数。例如 $f(1960)=f(2^3\times 5^1\times 7^2)=3,f(10007)=1,f(1)=0$。 给定正整数 a,ba,b,求下式的值:

i=1aj=1bf(gcd(i,j))\sum_{i=1}^a\sum_{j=1}^b f(gcd(i,j))

输入格式

第一行一个数 TT,表示询问数。

接下来 TT 行,每行两个数 a,ba,b,表示一个询问。

输出格式

对于每一个询问,输出一行一个非负整数作为回答。

4
7558588 9653114
6514903 4451211
7425644 1189442
6335198 4957
35793453939901
14225956593420
4332838845846
15400094813

数据规模与约定

对于 100%100\% 的数据,1T1041\leq T\leq 10^41a,b1071\leq a,b\leq 10^7