bzoj 4407: 于神之怒加強版 莫比烏斯反演

題意

給出n,m,k求

多組資料

n,m<=5000000,T<=2000

分析

設d=gcd(i,j)

那麼ans=∑nd=1dk∗f(d)

f(d)表示1<=i<=n,1<=j<=m中gcd(i,j)=d的(i,j)對數

反演後可得ans=∑nd=1dk∑⌊nd⌋i=1μ(i)⌊ndi⌋⌊mdi⌋

設T=di則ans=∑nT=1⌊nT⌋⌊mt⌋∑d|Tdkμ(Td)

那麼隻要求出∑d|Tdkμ(Td)的字首和即可O(n√)詢問

設f(d)=dk,g(d)=μ(d),h(T)=∑d|Tf(d)g(Td)

顯然h為f和g的狄利克雷卷積，因為f和g均為積性函數，那麼h也為積性函數，那麼就可以用線性篩來求出h

low[i]表示i的最小質因子的其對應指數的次方。

代碼

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define N 5000005
#define ll long long
using namespace std;

const int MOD=;

int k,n,m,tot,prime[N],low[N],f[N];
bool not_prime[N];

int ksm(int x,int y)
{
    if (!y) return ;
    if (y==) return x;
    int w=ksm(x,y/);
    w=(ll)w*w%MOD;
    if (y%==) w=(ll)w*x%MOD;
    return w;
}

void prework(int n)
{
    f[]=;
    for (int i=;i<=n;i++)
    {
        if (!not_prime[i])
        {
            low[i]=prime[++tot]=i;
            f[i]=ksm(i,k)-;
        }
        for (int j=;j<=tot&&i*prime[j]<=n;j++)
        {
            not_prime[i*prime[j]]=;
            if (i%prime[j]==)
            {
                if (low[i]==i) f[i*prime[j]]=(ll)f[i]*(f[prime[j]]+)%MOD;
                else f[i*prime[j]]=(ll)f[low[i]*prime[j]]*f[i/low[i]]%MOD;
                low[i*prime[j]]=low[i]*prime[j];
                break;
            }
            f[i*prime[j]]=(ll)f[i]*f[prime[j]]%MOD;
            low[i*prime[j]]=prime[j];
        }
    }
    for (int i=;i<=n;i++)
        f[i]=(f[i-]+f[i])%MOD;
}

int main()
{
    int t;
    scanf("%d%d",&t,&k);
    prework();
    while (t--)
    {
        scanf("%d%d",&n,&m);
        if (n>m) swap(n,m);
        int ans=;
        for (int i=,last;i<=n;i=last+)
        {
            last=min(n/(n/i),m/(m/i));
            ans=(ans+(ll)(n/i)*(m/i)%MOD*(f[last]-f[i-])%MOD)%MOD;
        }
        printf("%d\n",(ans+MOD)%MOD);
    }
    return ;
}