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

不會搞數學公式很苦惱！！

flag：會寫數學公式之後一定好好寫一發題解

非常感謝龍爺（sd第一男選手！！可惜神犇都不寫blog）提供線性篩做法

2.16————————————————-

一下均設 n<=m

Ans=∑i=1n∑j=1mgcd(i,j)k

設 f(d) 為 gcd(x,y)=d 的 (x,y) 數對的數量

g(d)=∑i=1⌊nd⌋f(i∗d)=⌊nd⌋∗⌊md⌋

f(d)=∑i=1⌊nd⌋u(i)∗g(i∗d)=∑i=1⌊nd⌋u(i)∗⌊md∗i⌋∗⌊nd∗i⌋

Ans=∑d=1ndk∑i=1⌊nd⌋u(i)∗⌊md∗i⌋∗⌊nd∗i⌋

此時兩次分塊可以做到單次訊問 O(n) 但是還不夠

繼續等價變換令 T=d∗i

Ans=∑T=1n⌊nT⌋∗⌊mT⌋∑d|Tdk∗u(Td)

h(T)=∑d|Tdk∗u(Td)

隻需要搞出 h(T) 的字首和再用分塊處理就可以做到單次訊問 n−√ 的複雜度

然後就是鬼畜的線性篩，還要感謝龍爺

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<iostream>
#include<algorithm>
#define N 5000005
#define ll long long
#define R 1000000007ll
using namespace std;
int sc()
{
    int i=,f=; char c=getchar();
    while(c>'9'||c<'0'){if(f=='-')f=-;c=getchar();}
    while(c>='0'&&c<='9')i=i*10+c-'0',c=getchar();
    return i;
}
ll f[N],K;
int prime[N],low[N];
int a[N],n;
ll cal(ll x)
{
    ll ans=,y=K;
    while(y)
    {
        if(y&)ans=ans*x%R;
        x=x*x%R;
        y>>=;
    }
    return (ans-+R)%R;
}
void pre()
{
    int top=; f[]=low[]=;
    for(int i=;i<N;i++)
    {
        if(!a[i])
        {
            low[i]=prime[++top]=i;
            f[i]=cal(i);
        }
        for(int j=;i*prime[j]<N;j++)
        {
            a[i*prime[j]]=;
            if(i%prime[j]==)
            {
                low[i*prime[j]]=low[i]*prime[j];
                if(low[i]==i) 
                    f[i*prime[j]]=f[i]*(f[prime[j]]+)%R;
                else
                    f[i*prime[j]]=f[i/low[i]]*f[low[i]*prime[j]]%R;
                break;
            }
            low[i*prime[j]]=prime[j];
            f[i*prime[j]]=f[i]*f[prime[j]]%R;
        }
    }
    for(int i=;i<N;i++)f[i]=(f[i]+f[i-])%R;
}
int main()
{
    n=sc(),K=sc();
    pre();
    while(n--)
    {
        ll ans=;
        int n=sc(),m=sc();
        if(n>m)swap(n,m);
        for(int i=,last;i<=n;i=last+)
        {
            last=min(n/(n/i),m/(m/i));
            ans=(ans+((ll)(n/i)*(m/i)%R)*(R+f[last]-f[i-])%R)%R;
        }
        printf("%lld\n",ans);
    }
    return ;
}