A20931.Crash的数字表格
省选/NOI-
官方
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
今天的数学课上,Crash小朋友学习了最小公倍数(Least Common Multiple)。对于两个正整数 a 和 b,lcm(a,b) 表示能同时被 a 和 b 整除的最小正整数。例如,lcm(6,8)=24。
回到家后,Crash还在想着课上学的东西,为了研究最小公倍数,他画了一张n×m的表格。每个格子里写了一个数字,其中第 i 行第 j 列的那个格子里写着数为 lcm(i,j)。
看着这个表格,Crash想到了很多可以思考的问题。不过他最想解决的问题却是一个十分简单的问题:这个表格中所有数的和是多少。当 n 和 m 很大时,Crash就束手无策了,因此他找到了聪明的你用程序帮他解决这个问题。由于最终结果可能会很大,Crash只想知道表格里所有数的和对 20101009 取模后的值。
输入格式
输入包含一行两个整数,分别表示 n 和 m。
输出格式
输出一个正整数,表示表格中所有数的和对 20101009 取模后的值。
输入输出样例
输入#1
4 5
输出#1
122
说明/提示
样例输入输出 1 解释
该表格为:
1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|
2 | 2 | 6 | 4 | 10 |
3 | 6 | 3 | 12 | 15 |
4 | 4 | 12 | 4 | 20 |
数据规模与约定
- 对于 30% 的数据,保证 n,m≤103。
- 对于 70% 的数据,保证 n,m≤105。
- 对于 100% 的数据,保证 1≤n,m≤107。