题目描述

Description

给定正整数n,m。求

Input

一行两个整数n,m。

Output

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

Sample Input

5 4

Sample Output

424

HINT

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

题目分析

然后暴力更新即可 时间复杂度 n ln n

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
bool vis[500010];
int mu[500010],prime[500010];
int mod=1000000007; 
void init()
{
    mu[1]=1;
    for(int i=2;i<=500000;i++)
    {
        if(!vis[i]) prime[++prime[0]]=i,mu[i]=-1;
        for(int j=1;j<=prime[0],i*prime[j]<=500000;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]) mu[i*prime[j]]=-mu[i];
            else break;
        }
    }
}
long long ans;
long long ksm(long long x,int y)
{
    long long sum=1;
    while(y)
    {
        if(y&1) sum=sum*x%mod;
        y=y>>1,x=x*x%mod;
    }
    return sum;
}
long long sum[500010];
long long d[500010];
void work()
{
    for(int i=1;i<=m;i++) d[i]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m/i;j++) 
            d[j]=((long long)d[j]*j)%mod,sum[j]=(sum[j-1]+d[j])%mod;
        long long D=ksm((long long)i,i);

        for(int j=1;j<=n/i;j++)
            ans=(ans+(long long)mu[j]*D%mod*d[j]%mod*d[j]%mod*sum[(n/i)/j]%mod*sum[(m/i)/j]%mod+mod)%mod;
    }
    printf("%lld\n",ans%mod);
}
int main()
{   
    scanf("%d%d",&n,&m);
    if(n>m) swap(n,m);
    init(),work();
    return 0;
}