bzoj3561DZY Loves Math VI

3561: DZY Loves Math VI

Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 503 Solved: 333
[Submit][Status][Discuss]

Description

给定正整数n,m。求

Input

一行两个整数n,m。

Output

一个整数，为答案模1000000007后的值。

Sample Input

5 4

Sample Output

424

HINT

数据规模：

1<=n,m<=500000，共有3组数据。

Source

By Jcvb

莫比乌斯反演
http://blog.csdn.net/lych_cys/article/details/50721642?locationNum=1&fps=1

 #include<bits/stdc++.h>

 #define ll long long

 #define mod 1000000007

 #define N 500001

 using namespace std;

 int n,m,cnt,mo[N],p[N>>],vis[N];ll a[N],sum[N],ans;

 void predeal(){

     mo[]=;

     for(int i=;i<N;i++){

         if(!vis[i]){mo[i]=-;p[++cnt]=i;}

         for(int j=;j<=cnt&&i*p[j]<N;++j){

             vis[i*p[j]]=;

             if(i%p[j])mo[i*p[j]]=-mo[i];

             else{mo[i*p[j]]=;break;}

         }

     }

 }

 int quick(int a,int b){

     int ret=;

     while(b){

         if(b&)ret=1ll*a*ret%mod;

         a=1ll*a*a%mod;b>>=;

     }

     return ret;

 }

 int main(){

     scanf("%d%d",&n,&m);predeal();if(n>m)swap(n,m);

     for(int i=;i<N;i++)a[i]=;

     for(int i=;i<=n;i++){

         ll res=;

         for(int j=;j*i<=m;++j)

         a[j]=a[j]*j%mod,sum[j]=(sum[j-]+a[j])%mod;

         for(int j=;j*i<=n;++j)

         if(mo[j])res=(res+mo[j]*a[j]*a[j]%mod*sum[n/i/j]%mod*sum[m/i/j]%mod)%mod;

         ans=(ans+res*quick(i,i)%mod)%mod;

     }

     ans<?ans+=mod:;printf("%lld\n",ans);

     return ;

 }

巴特西