#P50339. 「SDOI2014」数表
「SDOI2014」数表
题目描述
有一张 的数表,其第 行第 列()的数值为能同时整除 和 的所有自然数之和。
给定 ,计算数表中不大于 的数之和。
输入格式
输入包含多组数据。
输入的第一行一个整数表示测试点内的数据组数。
接下来 行,每行三个整数 描述一组数据。
输出格式
对每组数据,输出一行一个整数,表示答案模 的值。
样例
2
4 4 3
10 10 5
20
148
数据范围与提示
对于所有数据,。
有一张 n×m 的数表,其第 i 行第 j 列(1≤i≤n,1≤j≤m)的数值为能同时整除 i 和 j 的所有自然数之和。
给定 a,计算数表中不大于 a 的数之和。
输入包含多组数据。
输入的第一行一个整数Q表示测试点内的数据组数。
接下来 Q 行,每行三个整数 n,m,a 描述一组数据。
对每组数据,输出一行一个整数,表示答案模 231 的值。
2
4 4 3
10 10 5
20
148
对于所有数据,1≤Q≤2×104, 1≤n,m≤105, a≤109。