首页 > 代码库 > 【bzoj4407】于神之怒加强版 莫比乌斯反演+线性筛

【bzoj4407】于神之怒加强版 莫比乌斯反演+线性筛

题目描述

给下N,M,K.求
技术分享

输入

输入有多组数据,输入数据的第一行两个正整数T,K,代表有T组数据,K的意义如上所示,下面第二行到第T+1行,每行为两个正整数N,M,其意义如上式所示。

输出

如题

样例输入

1 2
3 3

样例输出

20


题解

莫比乌斯反演+线性筛

$\sum\limits_{i=1}^n\sum\limits_{j=1}^m\gcd(i,j)^k\\=\sum\limits_{d=1}^{\min(n,m)}d^k\sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(i,j)=d]\\=\sum\limits_{d=1}^{\min(n,m)}d^k\sum\limits_{i=1}^{\lfloor\frac nd\rfloor}\sum\limits_{j=1}^{\lfloor\frac md\rfloor}[\gcd(i,j)=1]\\=\sum\limits_{d=1}^{\min(n,m)}d^k\sum\limits_{i=1}^{\lfloor\frac nd\rfloor}\sum\limits_{j=1}^{\lfloor\frac md\rfloor}\sum\limits_{t|gcd(i,j)}\mu(t)\\=\sum\limits_{d=1}^{\min(n,m)}d^k\sum\limits_{i=1}^{\lfloor\frac nd\rfloor}\sum\limits_{j=1}^{\lfloor\frac md\rfloor}\sum\limits_{t|i\&t|j}\mu(t)\\=\sum\limits_{d=1}^{\min(n,m)}d^k\sum\limits_{t=1}^{\lfloor\frac{\min(n,m)}d\rfloor}\mu(t)\lfloor\frac n{dt}\rfloor\lfloor\frac m{dt}\rfloor$

继续令$D=dt$,可以得到:

$\sum\limits_{d=1}^{\min(n,m)}d^k\sum\limits_{t=1}^{\lfloor\frac{\min(n,m)}d\rfloor}\mu(t)\lfloor\frac n{dt}\rfloor\lfloor\frac m{dt}\rfloor\\=\sum\limits_{D=1}^{\min(n,m)}\lfloor\frac nD\rfloor\lfloor\frac mD\rfloor\sum\limits_{d|D}d^k\mu(t)\\=\sum\limits_{D=1}^{\min(n,m)}\lfloor\frac nD\rfloor\lfloor\frac mD\rfloor f(D)\\(f(D)=\sum\limits_{d|D}d^k\mu(t))$

此时可以选择通过枚举倍数来预处理$f$数组,有个小优化:枚举时先枚举$t$,如果$\mu(t)=0$则不进行操作。这样预处理的时间复杂度为$O(n\ln n+n\log k)$,可以勉强通过本题。

然后我就被CQzhangyu大佬D了一顿= =

此时可以发现$f$是$id^k$与$\mu$的狄利克雷卷积,两个积性函数的狄利克雷卷积也是积性函数。于是可以快筛$f$函数。

当$i$为质数时,显然$f(i)=i^k-1$

考虑$i*p$(p是质数)的处理:

当$i\mod p\neq 0$时,显然$i$与$p$互质,就有$f(i*p)=f(i)*f(p)$

当$i\mod p=0$时,对$f(i*p)$有影响的$t$一定是与对$f(i)$有影响的$t$中,因为其余的因数都至少包含$p^2$,$\mu=0$。而此时$d$增加了$p$倍,故$f(i*p)=f(i)*p^k$。

综上可以线性筛出$f$函数,然后分块处理。时间复杂度为$O(n+\frac{n\log k}{\ln n}+T\sqrt(n))$

#include <cstdio>#include <cstring>#include <algorithm>#define N 5000010using namespace std;typedef long long ll;const int p = 5000000 , mod = 1000000007;int prime[N] , tot;ll d[N] , f[N] , sum[N];bool np[N];ll pow(ll x , ll y){    ll ans = 1;    while(y)    {        if(y & 1) ans = ans * x % mod;        x = x * x % mod , y >>= 1;    }    return ans;}int main(){    int T , k , i , j , n , m;    ll ans;    scanf("%d%d" , &T , &k);    f[1] = sum[1] = 1;    for(i = 2 ; i <= p ; i ++ )    {        if(!np[i]) prime[++tot] = i , d[tot] = pow(i , k) , f[i] = (d[tot] - 1 + mod) % mod;        for(j = 1 ; j <= tot && i * prime[j] <= p ; j ++ )        {            np[i * prime[j]] = 1;            if(i % prime[j] == 0)            {                f[i * prime[j]] = f[i] * d[j] % mod;                break;            }            else f[i * prime[j]] = f[i] * f[prime[j]] % mod;        }        sum[i] = (sum[i - 1] + f[i]) % mod;    }    while(T -- )    {        scanf("%d%d" , &n , &m) , ans = 0;        for(i = 1 ; i <= n && i <= m ; i = j + 1)            j = min(n / (n / i) , m / (m / i)) , ans = (ans + (ll)(n / i) * (m / i) % mod * (sum[j] - sum[i - 1] + mod)) % mod;        printf("%lld\n" , ans);    }    return 0;}

 

 

【bzoj4407】于神之怒加强版 莫比乌斯反演+线性筛