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

题目描述

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

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

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

输入格式

输入包含一行两个整数，分别表示 $n$ 和 $m$。

输出格式

输出一个正整数，表示表格中所有数的和 $\mathrm{mod}20101009$的值。

样例 #1

样例输入 #1

4 5

样例输出 #1

122

提示

样例输入输出 1 解释

该表格为：

数据规模与约定

• 对于 $30\%$ 的数据，保证 n,m≤103n, m \\le 10^3n,m≤103。
• 对于 $70\%$ 的数据，保证 n,m≤105n, m \\le 10^5n,m≤105。
• 对于 $100\%$ 的数据，保证 1≤n,m≤1071\\le n,m \\le 10^71≤n,m≤107。

思路：


AC代码：

在这里插入代码片
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const long long N=1e7+11;
long long s[N],m[N],sum[N],f[N];
long long cnt;
long long a[N];
long long p[N];
const long long mod=20101009;
inline int read()
{int s = 0,w = 1; char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}while(ch >= '0' && ch <= '9'){s =s * 10+ch - '0'; ch = getchar();}return s * w;
}
void unit(long long n){m[1]=1;for(long long i=2;i<=n;i++){if(!a[i]){s[++cnt]=i;m[i]=-1;}for(long long j=1;s[j]*i<=n&&j<=cnt;j++){
//			int op=s[j]*i;a[s[j]*i]=1;if(i%s[j]==0){
//				m[i*p[j]]=0;break;}m[s[j]*i]=m[i]*-1;}}for(long long i=1;i<=n;i++){sum[i]=(sum[i-1]+i*i%mod*(m[i]+mod))%mod;}
}
long long nn(long long x,long long y ){return ((x*(x+1)/2)%mod*((y*(y+1)/2)%mod))%mod;
}
long long calc(long long a,long long b)
{static long long max_rep;static long long ans;max_rep=min(a,b);ans=0;for(long long l=1,r;l<=max_rep;l=r+1){r=min(a/(a/l),b/(b/l));ans=(mod+ans+(1ll*nn(a/l,b/l)%mod*(sum[r]-sum[l-1])%mod)%mod)%mod;}return ans%mod;
}
long long solve(long long x,long long y){long long res=0;for(long long i=1,j;i<=min(x,y);i=j+1){j=min(x/(x/i),y/(y/i));res=(res+((j-i+1)*(i+j)/2%mod)*(calc(x/i,y/i)%mod))%mod;}return res%mod;
}
int main(){unit(N-10);long long t=1;while(t--){long long n=read();long long m=read();printf("%lld\\n",solve(n,m));}
}