[SDOI2015]约数个数和

题目简述

求：

$$\sum_{i=1}^n\sum_{j=1}^m\sigma(ij)$$

分析

$$\sigma(ij)=\sum_{x|i}\sum_{y|j}[x\perp y]$$

证明：

$$i=\prod_{k=1}{p_k}^{a_k},j=\prod_{k=1}{p_k}^{b_k}\\ ij=\prod_{k=1}{p_k}^{a_k+b_k},\sigma(ij)=\prod_{k=1}(a_k+b_k+1)$$

所以说，可以有这样的假设：

• 当 $x\perp y\;\;\land {a_k}^\prime>0$ 时，$x\times y$ 的 $p_k$ 的指数就是 ${a_k}^\prime$。
• 当 $x\perp y\;\;\land {b_k}^\prime>0$ 时，$x\times y$ 的 $p_k$ 的指数就是 $a_k+{b_k}^\prime$

所以这样可以不重不漏的枚举出所有 $ij$ 的约数。

化简

所以原式可以化为：

$$\begin{aligned} \sum_{i=1}^n\sum_{j=1}^m\sigma(ij)&=\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}[x\perp y]\\ &=\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}\sum_{d|\gcd(x,y)}\mu(d)\\ &=\sum_{d=1}^n\mu(d)\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac md\rfloor}\sigma(i)\sigma(j)\\ &=\sum_{d=1}^n\mu(d)\sum_{i=1}^{\lfloor\frac nd\rfloor}\sigma(i)\sum_{j=1}^{\lfloor\frac md\rfloor}\sigma(j)\\ &=\sum_{d=1}^n\mu(d)g(\lfloor\frac nd\rfloor)g(\lfloor\frac md\rfloor) \end{aligned}$$

所以就是 $O(n)$ 的预处理 $+\;O(T\sqrt n)$ 的查询，这道题就愉快的结束了。

Code

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int Maxn = 5e4;
int Cnt, Prim[Maxn + 5], Mu[Maxn + 5], C[Maxn + 5];
ll D[Maxn];
bool Vis[Maxn + 5];
int T, N, M;

inline void Init()
{
    Mu[1] = D[1] = C[1] = 1;
    for (int i = 2; i <= Maxn; ++i)
    {
        if (!Vis[i]) Prim[++Cnt] = i, Mu[i] = -1, C[i] = 1, D[i] = 2;
        for (int j = 1; j <= Cnt && i * Prim[j] <= Maxn; ++j)
        {
            Vis[i * Prim[j]] = 1;
            if (i % Prim[j] == 0)
            {
                D[i * Prim[j]] = D[i] / (C[i] + 1) * (C[i] + 2);
                C[i * Prim[j]] = C[i] + 1;
                break;
            }
            Mu[i * Prim[j]] = -Mu[i];
            D[i * Prim[j]] = D[i] << 1;
            C[i * Prim[j]] = 1;
        }
        Mu[i] += Mu[i - 1], D[i] += D[i - 1];
    }
}

inline int read()
{
    int x(0);
    char o(getchar());
    while (o < '0' || o > '9') o = getchar();
    for (; o >= '0' && o <= '9'; o = getchar())
        x = (x << 1) + (x << 3) + (o ^ 48);
    return x;
}

int main()
{
    Init();
    T = read();    
    while (T--)
    {
        N = read(), M = read();        
        if (N > M) swap(N, M);
        ll Ans(0);
        for (int l = 1, r; l <= N; l = r + 1)
        {
            r = min(N / (N / l), M / (M / l));
            Ans += (Mu[r] - Mu[l - 1]) * D[N / l] * D[M / l];
        }
        printf("%lld\n", Ans);
    }
}