#P2693. jzptab

    ID: 1787 传统题 1000ms 512MiB 尝试: 2414 已通过: 598 难度: 7 上传者: 标签>CF2300提高+/省选-莫比乌斯反演交换求和顺序筛法计算积性函数线性筛一维前缀和整除分块等差数列求和

jzptab

题目描述

求 $\sum^{n}_{i=1} \sum^{m}_{j=1} \operatorname{lcm}(i,j)$,对答案  mod 108+9\bmod 10^8+9。

输入格式

一个正整数 TT 表示数据组数。

接下来 TT 行,每行两个正整数,表示 n,mn,m。

输出格式

TT 行,每行一个整数,表示第 ii 组数据的结果。

1
4 5
122

数据规模与约定

1≤T≤1041\le T \le 10^4,1≤n,m≤1071\le n,m \le 10^7。