Problem Description

今天的數學課上，Crash小朋友學習了最小公倍數(Least Common Multiple)。對于兩個正整數a和b，LCM(a, b)表示能同時被a和b整除的最小正整數。例如，LCM(6, 8) = 24。回到家后，Crash還在想著課上學的東西，為了研究最小公倍數，他畫了一張N*M的表格。每個格子里寫了一個數字，其中第i行第j列的那個格子里寫著數為LCM(i, j)。

一個4*5的表格如下：

1	2	3	4	5
2	2	6	4	10
3	6	3	12	15
4	4	12	4	20

看著這個表格，Crash想到了很多可以思考的問題。不過他最想解決的問題卻是一個十分簡單的問題：這個表格中所有數的和是多少。當N和M很大時，Crash就束手無策了，因此他找到了聰明的你用程序幫他解決這個問題。由于最終結果可能會很大，Crash只想知道表格里所有數的和mod 20101009的值。

Input

輸入的第一行包含兩個正整數，分別表示N和M。

100%的數據滿足N, M ≤ 10^7。

Output

輸出一個正整數，表示表格中所有數的和mod 20101009的值。

Examples

Input

4 5

Output

122

思路：

題目本質是給出 n、m 兩個數，求?

由于?，因此?

將 gcd(i,j) 提出來，有：

把 d 提出來，有：

設?，則有：

設?，那么，

再設?

可以看出，f(d)、g(d) 符合莫比烏斯反演的倍數關系，即：

對 g(d) 進行化簡，有：

那么，

因此，需要預處理 u(i)*i^2 的前綴和，然后利用整除分塊求出后面的 ij 的和算出 f(1) 后，再計算 res

Source Program

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<bitset> #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long #define Pair pair<int,int> LL quickPow(LL a,LL b){ LL res=1; while(b){if(b&1)res*=a; a*=a; b>>=1;} return res; } LL quickModPow(LL a,LL b,LL mod){ LL res=1; a=a%mod; while(b){if(b&1)res=(a*res)%mod; a=(a*a)%mod; b>>=1;} return res; } LL getInv(LL a,LL mod){ return quickModPow(a,mod-2,mod); } const double EPS = 1E-10; const int MOD = 20101009; const int N = 12000000+5; const int dx[] = {-1,1,0,0,-1,-1,1,1}; const int dy[] = {0,0,-1,1,-1,1,-1,1}; using namespace std;int mu[N]; int prime[N]; bool bprime[N]; int cnt; LL sum[N]; void getMu(int n){//線性篩求莫比烏斯函數cnt=0;mu[1]=1;//根據定義，μ(1)=1memset(bprime,false,sizeof(bprime));for(int i=2;i<=n;i++){//求2~n的莫比烏斯函數if(!bprime[i]){prime[++cnt]=i;//存儲質數mu[i]=-1;//i為質數時，μ(1)=-1}for(int j=1;j<=cnt&&i*prime[j]<=n;j++){//枚舉i之前的素數個數bprime[i*prime[j]]=true;//不是質數if(i%prime[j])//i不是prime[j]的整數倍時，i*prime[j]就不會包含相同質因子mu[i*prime[j]]=-mu[i];//mu[k]=mu[i]*mu[prime[j]]，因為prime[j]是質數，mu值為-1else{mu[i*prime[j]]=0;break;//留到后面再篩}}} } LL cal(LL n,LL m){LL res=0;LL minn=min(n,m);for(LL left=1,right;left<=minn;left=right+1){right=min(n/(n/left),m/(m/left));LL G=( ((1+n/left)*(n/left)/2)%MOD ) * ( ((1+m/left)*(m/left)/2)%MOD ) %MOD;res=( res+((sum[right]-sum[left-1])%MOD*G%MOD)%MOD )%MOD;}return (res+MOD)%MOD; } int main(){getMu(12000000);LL n,m;scanf("%lld%lld",&n,&m);LL minn=min(n,m);for(LL i=1;i<=minn;i++){LL temp=(((i%MOD*i%MOD)%MOD)%MOD*mu[i]%MOD)%MOD;sum[i]=(sum[i-1]+temp+MOD)%MOD;}LL res=0;for(LL left=1,right;left<=minn;left=right+1){right=min(n/(n/left),m/(m/left));LL temp=(left+right)*(right-left+1)/2%MOD;res=(res+(cal(n/left,m/left)%MOD*temp%MOD)%MOD)%MOD;}printf("%lld\n",res);// system("pause");return 0; }

?

總結

以上是生活随笔為你收集整理的Crash的数字表格（HYSBZ-2154）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。