#P3309. DZY Loves Math

    ID: 2497 传统题 4000ms 512MiB 尝试: 1875 已通过: 904 难度: 8 上传者: 标签>CF2400提高+/省选-莫比乌斯反演狄利克雷卷积交换求和顺序线性筛一维前缀和整除分块

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=1a∑j=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\% 的数据,1≤T≤1041\leq T\leq 10^4,1≤a,b≤1071\leq a,b\leq 10^7。