P3768 简单的数学题

P3768 简单的数学题

题解

题意

给定$n,p$ 求：

$$\bigg( \sum_{i = 1}^n \sum_{j =1}^n i j \gcd(i,j) \bigg) \bmod p$$

其中，$n \le 10 ^ {10}, 5.8 \times 10 ^ 8 \le p \le 1.1 \times 10 ^ 9$

解法

首先观察到$n$ 的数据范围，肯定是要以一个亚线性时间复杂度跑过去的，须有用到杜教筛或Min_25筛，这里用的杜教筛。

首先化简式子：

$$\begin{aligned} \sum_{i = 1}^n \sum_{j =1}^n i j \gcd(i,j) & = \sum_{d = 1}^n d \sum_{i = 1}^n \sum_{j = 1}^n ij \left[ \gcd(i,j) == d \right] \\ & = \sum_{d = 1}^n d^3 \sum_{i = 1}^{\left\lfloor \frac{n}{d}\right\rfloor} \sum_{j = 1}^{\left\lfloor \frac{n}{d} \right\rfloor} i j \left[ \gcd(i,j) == 1 \right] \\ \end{aligned}$$

后面是个经典的式子，设为$S(n)$，接着化简：

$$\begin{aligned} S(n) & = \sum_{i = 1}^{n} \sum_{j = 1}^{n} i j \left[ \gcd(i,j) == 1 \right] \\ & = \sum_{i = 1}^{n} \sum_{j = 1}^{n} i j \sum_{d \mid \gcd(i,j)} \mu(d) \\ & = \sum_{d = 1}^{n} \mu(d) d^2 \sum_{i = 1}^{\left\lfloor \frac{n}{d}\right\rfloor} \sum_{j = 1}^{\left\lfloor \frac{n}{d} \right\rfloor} 1 \end{aligned}$$

后面的式子可以$O(1)$处理，再套上一个数论分块，然后就可以得到60分了，然而这并不能解决这道题，其实可以在其中的一步换一种方式去卷mu，但是有更简单的做法，重新考虑式子，对其使用欧拉反演：

有：

$$\varphi \ast 1 = Id$$

即：

$$\sum_{d\mid n}\varphi(d) = n$$

原来的式子可以化为：

$$\begin{aligned} \sum_{i = 1}^n \sum_{j = 1}^n i j \gcd(i,j) & = \sum_{i = 1}^n \sum_{j = 1}^n i j \sum_{d\mid i, d\mid j}\varphi(d) \\ & = \sum_{d = 1}^n \varphi(d) d^2 \sum_{i = 1}^{\left\lfloor \frac{n}{d}\right\rfloor} \sum_{j = 1}^{\left\lfloor \frac{n}{d} \right\rfloor} i j \end{aligned}$$

显然后面的式子可以$O(1)$计算，

$$\frac{n^2 (n+1)^2}{4}$$

现在考虑如何计算前面的

$$\sum_{d = 1}^n \varphi(d) d^2$$

既然$\varphi \ast 1 = Id$,将$\varphi(d)d^2$设为$f$,设$g = Id^2$显然有

$$\bigg(f \ast g\bigg)n = \sum_{d \mid n} \varphi(d)d^2 (\frac{n}{d})^2 = n ^3$$

看来问题已经解决了，$S(n)$为我们想要求的和，

$$\sum_{i = 1}^n\bigg( f\ast g \bigg)i = \sum_{i = 1} ^ n g(i) S(\left\lfloor \frac{n}{i} \right\rfloor) = \sum_{i = 1}^n i ^ 3$$

然后使用技巧，

$$g(1)S(n) = \sum_{i = 1}^n\bigg( f\ast g \bigg)i - \sum_{i = 2}^ng(i)S(\left\lfloor \frac{n}{i}\right\rfloor)$$

又因为$g(1) = 1$,得到递归式，

$$S(n) = \sum_{i = 1}^n\bigg( f\ast g \bigg)i - \sum_{i = 2}^ng(i)S(\left\lfloor \frac{n}{i}\right\rfloor)$$

需要用到：

$$\sum_{i = 1}^n i ^2 = \frac{n(n+1)(2n+1)}{6} \\ \sum_{i = 1}^n i ^3 = \frac{n^2 (n+1)^2}{4}$$

用杜教筛，时间复杂度$O(n^{\frac{2}{3}})$

#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;

#define int long long

const int N = 5e6 + 10;

int mod;

int inv4, inv6;

inline int qpow(int a, int b)
{
    int t = 1;
    while(b != 0)
    {
        if(b & 1)t = t * a%mod;
        a = a * a%mod; b >>= 1;
    }
    return t%mod;
}

int cnt, prime[N], phi[N];

int S_phi[N];

bool vis[N];

inline void init(int n)
{
    phi[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        if(!vis[i])
        {
            prime[++cnt] = i;
            phi[i] = i - 1;
        }
        for(int j = 1; j <= cnt && prime[j] * i <= n; j++)
        {
            vis[i * prime[j]] = true;
            if(i % prime[j] == 0)
            {
                phi[i * prime[j]] = prime[j] * phi[i];
                break;
            }
            phi[i * prime[j]] = phi[i] * phi[prime[j]];
        }
    }
    for(int i = 1; i <= n; i++)
        S_phi[i] = (S_phi[i-1] + phi[i]%mod * i%mod * i%mod)%mod;
}

inline int f(int n)
{
    return n %mod* n%mod * (n + 1ll)%mod * (n + 1)%mod *inv4 %mod;
}

inline int g(int n)
{
    return n%mod * (n + 1)%mod * (n * 2ll%mod + 1ll)%mod *inv6 %mod;
}

unordered_map<int, int> Phi;

int S(int n)
{
    if(n <= 5e6)return S_phi[n]%mod;
    if(Phi.count(n))return Phi[n];
    int sum = f(n)%mod;
    for(int l = 2, r; l <= n; l = r + 1)
    {
        r = n/(n/l);
        sum = (sum - S(n/l)%mod * (g(r) - g(l-1)) %mod + mod)%mod;
    }
    return Phi[n] = sum;
}

signed main()
{
    int n;
    scanf("%lld%lld", &mod, &n);
    inv4 = qpow(4, mod-2);
    inv6 = qpow(6, mod-2);
    init(5e6);
    int ans = 0;
    for(int l = 1, r; l <= n; l = r + 1)
    {
        r = n/(n/l);
        ans = (ans + f(n/l)%mod * (S(r) - S(l-1) + mod)%mod)%mod;
    }
    printf("%lld", ans);
    return 0;
}

tips: 欧拉反演的证明

$$\sum_{d \mid n} \varphi(d) = n$$

设$f(n) = \sum_{d \mid n} \varphi(d)$， $m \perp n$，根据欧拉函数的积性函数的性质有：

$$\begin{aligned} f(n) \times f(m) & = \sum_{i \mid n} \varphi(i) \sum_{j \mid m} \varphi(j) \\ & = \sum_{i \mid n} \sum_{j \mid m} \varphi(i) \varphi(j) \\ & = \sum_{i \mid n} \sum_{j \mid m} \varphi(ij) \\ & = \sum_{d \mid nm} \varphi(d) \\ & = f(nm) \end{aligned}$$

将$n$质因数分解$p_1 ^ {c_{1}} \times p_2 ^ {c_{2}} \times p_3 ^ {c_{3}} \times \cdots \times p_k ^ {c_{k}}$。

所以有，

$$f(n) = f(p_1 ^ {c_{1}}) \times f(p_2 ^ {c_{2}}) \times \cdots \times f(p_k ^ {c_{k}})$$

其中的每一项有：

$$f(p ^ c) = \sum_{i = 0}^ c \varphi(p^i) = p^c$$

所以得证：

$$f(n) = f(p_1 ^ {c_{1}}) \times f(p_2 ^ {c_{2}}) \times \cdots \times f(p_k ^ {c_{k}}) = \Pi_{i =1}^k p_i^{c_i} = n = \sum_{d \mid n} \varphi(d)$$