洛谷P3327-約數個數和-莫比烏斯反演+約數個數函數字首和

推式子

a n s = ∑ i = 1 N ∑ j = 1 M d ( i j ) \begin{aligned} ans= \sum_{i=1}^{N}\sum_{j=1}^{M}d(ij) \end{aligned} ans=i=1∑N​j=1∑M​d(ij)​

現在有個式子：

d ( i j ) = ∑ x ∣ i ∑ y ∣ j [ gcd ⁡ ( x , y ) = = 1 ] \begin{aligned} d(ij)= \sum_{x \mid i}\sum_{y \mid j}[\gcd(x,y)==1] \end{aligned} d(ij)=x∣i∑​y∣j∑​[gcd(x,y)==1]​

是以：

a n s = ∑ i = 1 N ∑ j = 1 M ∑ x ∣ i ∑ y ∣ j [ gcd ⁡ ( x , y ) = = 1 ] \begin{aligned} ans= \sum_{i=1}^{N}\sum_{j=1}^{M}\sum_{x \mid i}\sum_{y \mid j}[\gcd(x,y)==1] \end{aligned} ans=i=1∑N​j=1∑M​x∣i∑​y∣j∑​[gcd(x,y)==1]​

給 [ gcd ⁡ ( x , y ) = = 1 ] [\gcd(x,y)==1] [gcd(x,y)==1]替換掉：

a n s = ∑ d = 1 min ⁡ ( N , M ) μ ( d ) ∑ i = 1 N ∑ j = 1 M ∑ x ∣ i ∑ y ∣ j [ d ∣ gcd ⁡ ( x , y ) ] \begin{aligned} ans= \sum_{d=1}^{\min(N,M)}\mu(d)\sum_{i=1}^{N}\sum_{j=1}^{M}\sum_{x \mid i}\sum_{y \mid j}[d \mid \gcd(x,y)] \end{aligned} ans=d=1∑min(N,M)​μ(d)i=1∑N​j=1∑M​x∣i∑​y∣j∑​[d∣gcd(x,y)]​

我們枚舉 x x x, y y y:

a n s = ∑ d = 1 min ⁡ ( N , M ) μ ( d ) ∑ x = 1 N ∑ y = 1 M [ d ∣ gcd ⁡ ( x , y ) ] ⌊ N x ⌋ ⌊ M y ⌋ \begin{aligned} ans= \sum_{d=1}^{\min(N,M)}\mu(d)\sum_{x=1}^{N}\sum_{y=1}^{M}[d \mid \gcd(x,y)]\lfloor\frac{N}{x}\rfloor\lfloor\frac{M}{y}\rfloor \end{aligned} ans=d=1∑min(N,M)​μ(d)x=1∑N​y=1∑M​[d∣gcd(x,y)]⌊xN​⌋⌊yM​⌋​

a n s = ∑ d = 1 min ⁡ ( N , M ) μ ( d ) ∑ x = 1 ⌊ N d ⌋ ∑ y = 1 ⌊ M d ⌋ ⌊ N x d ⌋ ⌊ M y d ⌋ \begin{aligned} ans= \sum_{d=1}^{\min(N,M)}\mu(d)\sum_{x=1}^{\lfloor\frac{N}{d}\rfloor}\sum_{y=1}^{\lfloor\frac{M}{d}\rfloor}\lfloor\frac{N}{xd}\rfloor\lfloor\frac{M}{yd}\rfloor \end{aligned} ans=d=1∑min(N,M)​μ(d)x=1∑⌊dN​⌋​y=1∑⌊dM​⌋​⌊xdN​⌋⌊ydM​⌋​

a n s = ∑ d = 1 min ⁡ ( N , M ) μ ( d ) ∑ x = 1 ⌊ N d ⌋ ⌊ N x d ⌋ ∑ y = 1 ⌊ M d ⌋ ⌊ M y d ⌋ \begin{aligned} ans= \sum_{d=1}^{\min(N,M)}\mu(d)\sum_{x=1}^{\lfloor\frac{N}{d}\rfloor}\lfloor\frac{N}{xd}\rfloor\sum_{y=1}^{\lfloor\frac{M}{d}\rfloor}\lfloor\frac{M}{yd}\rfloor \end{aligned} ans=d=1∑min(N,M)​μ(d)x=1∑⌊dN​⌋​⌊xdN​⌋y=1∑⌊dM​⌋​⌊ydM​⌋​

我們令 f ( i ) = ∑ i = 1 n ⌊ n i ⌋ f(i)=\sum_{i=1}^{n}\lfloor\frac{n}{i}\rfloor f(i)=∑i=1n​⌊in​⌋

a n s = ∑ d = 1 min ⁡ ( N , M ) μ ( d ) f ( ⌊ N i ⌋ ) f ( ⌊ M i ⌋ ) \begin{aligned} ans= \sum_{d=1}^{\min(N,M)}\mu(d)f(\lfloor\frac{N}{i}\rfloor)f(\lfloor\frac{M}{i}\rfloor) \end{aligned} ans=d=1∑min(N,M)​μ(d)f(⌊iN​⌋)f(⌊iM​⌋)​

f ( n ) f(n) f(n)就是約數個數函數的字首和，我們預處理可以 O ( 1 ) O(1) O(1)查詢，然後分塊求 a n s ans ans

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T>
void out(T x) { cout << x << endl; }
ll fast_pow(ll a, ll b, ll p) {ll c = 1; while(b) { if(b & 1) c = c * a % p; a = a * a % p; b >>= 1;} return c;}
ll exgcd(ll a, ll b, ll &x, ll &y) { if(!b) {x = 1; y = 0; return a; } ll gcd = exgcd(b, a % b, y, x); y-= a / b * x; return gcd; }
const int N = 5e4 + 100;
int sum[N], d[N], mu[N], prime[N], tot;
//d[i]表示i的約數個數
//sum[i]表示i的最小質因子的最高次幂（線性篩用的是最小質因子去篩的）
bool mark[N];
void get_d_mu()
{
    mark[1] = mark[0] = true;
    tot = 0;
    mu[1] = d[1] = sum[1] = 1;
    for(int i = 2; i < N; i ++)
    {
        if(!mark[i])
        {
            prime[tot ++] = i;
            mu[i] = -1;
            d[i] = 2;
            sum[i] = 1;
        }
        for(int j = 0; j < tot && i * prime[j] < N; j ++)
        {
            mark[i * prime[j]] = true;
            if(i % prime[j] == 0)
            {
                d[i * prime[j]] = d[i] / (sum[i] + 1) * (sum[i] + 2);
                sum[i * prime[j]] = sum[i] + 1;
                mu[i * prime[j]] = 0;
                break;
            }
            mu[i * prime[j]] = -mu[i];
            d[i * prime[j]] = 2 * d[i];
            sum[i * prime[j]] = 1;
        }
    }
    for(int i = 1; i < N; i ++)
    {
        mu[i] += mu[i - 1];
        d[i] += d[i - 1];
    }
}
ll cal(ll n, ll m)
{
    if(n > m)
        swap(n, m);
    ll ans = 0;
    for(ll i = 1, j = 1; i <= n; i = j + 1)
    {
        j = min(n / (n / i), m / (m / i));
        ans += 1ll * (mu[j] - mu[i - 1]) * d[n / i] * d[m / i];
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    get_d_mu();
    int t;
    cin >> t;
    while(t --)
    {
        ll n, m;
        cin >> n >> m;
        cout << cal(n, m) << endl;
    }
}