#P3529. [Sdoi2014]数表

    ID: 2740 传统题 1000ms 512MiB 尝试: 3400 已通过: 1210 难度: 8 上传者: 标签>难度分类提高+/省选-数论莫比乌斯反演狄利克雷卷积构造与建模交换求和顺序离线与分治离线查询数据结构树状数组整除分块倍数枚举线性筛CF2400

[Sdoi2014]数表

[SDOI2014] 数表

题目描述

有一张 nn 行 mm 列的数表。第 ii 行第 jj 列的数值为 ii 和 jj 的所有正公因数之和。

对于给定的整数 aa,求表中所有不大于 aa 的格子数值的总和。同一数值出现在多个格子时,每个格子都要计入。

输入格式

第一行有一个整数 QQ,表示数据组数。接下来 QQ 行,每行有三个整数 n,m,an,m,a。

输出格式

每组数据输出一行一个整数,表示所求总和对 2312^{31} 取模后的结果。

样例 #1

2
4 4 3
10 10 5
20
148

数据范围

∣a∣≤109|a|\le10^9。原赛各测试点的规模如下。

测试点 n,mn,m QQ
1–3 1≤n,m≤4001\le n,m\le400 1≤Q≤2001\le Q\le200
4–6 1≤n,m≤1051\le n,m\le10^5 1≤Q≤101\le Q\le10
7–10 1≤Q≤2×1041\le Q\le2\times10^4