BZOJ4407: 于神之怒加强版

Description

给下N,M,K.求

Input

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

Output

如题

Sample Input

1 2
3 3

Sample Output

HINT

1<=N,M,K<=5000000,1<=T<=2000

Solution

首先可以推一波式子
\[ \begin{aligned} &\sum_{i=1}^{n}\sum_{j=1}^m(i,j)^k\\ &=\sum_{d=1}^nd^k\sum_{i=1}^{n}\sum_{j=1}^m[(i,j)=1]\\ &=\sum_{d=1}^nd^k\sum_{i=1}^{n}\sum_{j=1}^m\sum_{x|(i,j)}\mu(x)\\ &=\sum_{d=1}^nd^k\sum_{x=1}^n\mu(x)\lfloor\frac{n}{dx}\rfloor\lfloor\frac{m}{dx}\rfloor \end{aligned} \]
发现\(d^k\)是个完全积性函数，那么可以\(O(\sqrt{n}*\sqrt{n})=O(n)\)完成单次询问了

但是这样跑不过

所以继续推
\[ \begin{aligned} &设T=dx\\ &=\sum_{d=1}^nd^k\sum_{x=1}^n\mu(x)\lfloor\frac{n}{dx}\rfloor\lfloor\frac{m}{dx}\rfloor\\ &=\sum_{T=1}^{n}\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum_{d|T}\mu(\frac{T}{d})d^k \end{aligned} \]
发现后面那个玩意可以\(nlogn\)筛出来，那么可以做到\(O(nlogn+T\sqrt{n})\)，但是我被bzoj的土豆机卡了。。。所以要继续推。

研究一下后面那堆发现这是个狄利克雷卷积的形式，所以说这是个积性函数，但是莫比乌斯函数里面有个分数的话有点难写，于是根据狄利克雷卷积的定义改一下
\[ \begin{aligned} &设g(T)=\sum_{x|T}\mu(x)*(\frac{T}{x})^k\\ &g(i)=T^k*\sum_{x|T}\frac{\mu(x)}{x^k} \end{aligned} \]
考虑当T为质数的情况，设此时的\(T=p\)
\[ \begin{aligned} g(p) &=p^k*\sum_{x|p}\frac{\mu(x)}{x^k}\\ &=p^k*\left(\frac{\mu(1)}{1^k}+\frac{\mu(p)}{p^k}\right)\\ &=p^k*(1-\frac{1}{p^k})\\ &=p^k*\frac{p^k-1}{p^k}\\ &=p^k-1 \end{aligned} \]
因为\(g\)是一个积性函数，所以当i,j互质显然有
\[ g(i*j)=g(i)*g(j) \]
考虑\(j\)为\(i\)的质因数的情况（因为在线性筛过程中\(j\)必为质数）
\[ \begin{aligned} &设i=r*j^c(k内不含质因子j)\\ &g(i*j)\\ &=g(r*j^{c+1})\\ &=g(r)*g(j^{c+1})\\ &考虑g(j^{c+1})=\sum_{x|j^{c+1}}\frac{\mu(x)}{x^k}\\ &显然只有当x=1或j时\mu(x)才为1，其他情况为0所以当j的指数大于2时，g值是相同的\\ &所以g(j^{c+1})=g(j^c)\\ &又因为r和j^{c+1}和j^c互质，所以有\\ &g(i*j)=g(r*j^{c+1})=g(r)*g(j^{c+1})=g(r)*g(j^c)=g(r*j^c)=g(i) \end{aligned} \]
综上可得，在线性筛过程中
\[ g(i*prime[j])= \begin{cases} g(i)*g(prime[j])(i与prime[j]互质)\\ g(i)(prime[j]为i的质因子) \end{cases} \]
所以我们用线性筛筛出这个函数\(g\)，就可以\(O(n+T\sqrt{n})\)的效率了

这题我写了大半天...主要就卡在最后这个积性函数的推导...

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
#define N 5000050
 
ll n, m;
ll p[N], cnt, mu[N];
bool vis[N];
ll F[N], k, id[N], sum[N];
 
ll power(ll a, ll b) { ll ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans % mod;
}

void init() {
    cnt = 0;
    mu[1] = id[1] = F[1] = 1;
    for(ll i = 2; i < N; ++i) {
        if(!vis[i]) 
            id[i] = power(i, k) % mod, mu[i] = -1, p[++cnt] = i, F[i] = ((id[i] - 1) * power(id[i], mod - 2) + mod) % mod;
        for(ll j = 1; j <= cnt && 1ll * p[j] * i < N; ++j) {
            vis[i * p[j]] = 1;
            id[i * p[j]] = id[i] * id[p[j]] % mod;
            if(i % p[j] == 0) { F[i * p[j]] = F[i] % mod; break; }
            mu[i * p[j]] = -mu[i]; 
            F[i * p[j]] = F[i] * F[p[j]] % mod;
        }
    }
    for(ll i = 1; i < N; ++i) sum[i] = (sum[i - 1] + F[i] * id[i] % mod) % mod;
} 
 
ll calc(ll n, ll m) {
    ll ans = 0;
    if(n > m) swap(n, m);
    for(ll l = 1, r; l <= n; l = r + 1) {
        r = min(n / (n / l), m / (m / l));
        ans += 1ll * (n / l) % mod * (m / l) % mod * (sum[r] - sum[l - 1] + mod) % mod;
    }
    return ans % mod;
}
 
int main() {
    int T; scanf("%d%lld", &T, &k);
    init();
    while(T--) {
        scanf("%lld%lld", &n, &m);
        printf("%lld\n", (calc(n, m) + mod) % mod);
    }
}