#P1829. [国家集训队] Crash的数字表格 / JZPTAB

    ID: 4932 远端评测题 2000ms 500MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>数学2010WC/CTSC/集训队O2优化莫比乌斯反演

[国家集训队] Crash的数字表格 / JZPTAB

题目描述

今天的数学课上,Crash 小朋友学习了最小公倍数(Least Common Multiple)。对于两个正整数 aabblcm(a,b)\text{lcm}(a,b) 表示能同时整除 aabb 的最小正整数。例如,lcm(6,8)=24\text{lcm}(6, 8) = 24

回到家后,Crash 还在想着课上学的东西,为了研究最小公倍数,他画了一张 n×m n \times m 的表格。每个格子里写了一个数字,其中第 ii 行第 jj 列的那个格子里写着数为 lcm(i,j)\text{lcm}(i, j)

看着这个表格,Crash 想到了很多可以思考的问题。不过他最想解决的问题却是一个十分简单的问题:这个表格中所有数的和是多少。当 nnmm 很大时,Crash 就束手无策了,因此他找到了聪明的你用程序帮他解决这个问题。由于最终结果可能会很大,Crash 只想知道表格里所有数的和 mod20101009\bmod 20101009 的值。

输入格式

输入包含一行两个整数,分别表示 nnmm

输出格式

输出一个正整数,表示表格中所有数的和 mod20101009\bmod 20101009的值。

4 5
122

提示

样例输入输出 1 解释

该表格为:

11 22 33 44 55
22 66 44 1010
33 66 33 1212 1515
44 1212 44 2020

数据规模与约定

  • 对于 30%30\% 的数据,保证 n,m103n, m \le 10^3
  • 对于 70%70\% 的数据,保证 n,m105n, m \le 10^5
  • 对于 100%100\% 的数据,保证 1n,m1071\le n,m \le 10^7