P6825 「EZEC-4」求和

P6825 「EZEC-4」求和

$$
\begin {aligned}
\sum _ {i = 1} ^ n \sum _ {j = 1} ^ n (i, j) ^ {i + j} & = \sum _ {d = 1} ^ n \sum _ {i = 1} ^ n \sum _ {j = 1} ^ n [(i, j) = d] d ^ {i + j} \\
& = \sum _ {d = 1} ^ n \sum _ {i = 1} ^ {\lfloor \frac n d \rfloor } \sum _ {j = 1} ^ {\lfloor \frac n d \rfloor } [(i, j) = 1] d ^ {id + jd} \\
& = \sum _ {d = 1} ^ n \sum _ {i = 1} ^ {\lfloor \frac n d \rfloor } \sum _ {j = 1} ^ {\lfloor \frac n d \rfloor } \sum _ {k | (i, j)}\mu(k) d ^ {id + jd} \\
& = \sum _ {d = 1} ^ n \sum _ {k = 1} ^ n \mu(k) \sum _ {i = 1} ^ {\lfloor \frac n {kd} \rfloor } \sum _ {j = 1} ^ {\lfloor \frac n {kd} \rfloor } d ^ {id + jd} \\
& = \sum _ {d = 1} ^ n \sum _ {k = 1} ^ {\lfloor \frac n d \rfloor } \mu(k) (\sum _ {i = 1} ^ {\lfloor \frac n {kd} \rfloor } d ^ {id}) ^ 2 \\
\end {aligned}
$$

最后部分可以用等比数列算。于是可以做到 $O(n \ln n \log p)$ 。

查看代码

#include <cstdio>
using namespace std;
template <class Type>
void read (Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type, class ...rest>
void read (Type &x, rest &...y) { read(x), read(y...); }
template <class Type>
void write (Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar('0' + x % 10);
}
typedef long long LL;
const int N = 15e5 + 10;
bool vis[N];
int n, cnt, p[N], f[N], mod;
int binpow (int b, int k = mod - 2)
{
    int res = 1;
    for (; k; k >>= 1, b = (LL)b * b % mod)
        if (k & 1) res = (LL)res * b % mod;
    return res;
}
void init ()
{
    f[1] = 1;
    vis[1] = true;
    for (int i = 2; i < N; ++i)
    {
        if (!vis[i]) f[p[++cnt] = i] = -1;
        for (int j = 1; j <= cnt && i * p[j] < N; ++j)
        {
            vis[i * p[j]] = true;
            if (i % p[j] == 0) break;
            f[i * p[j]] = -f[i];
        }
    }
}
int main ()
{
    init();
    int T; read(T);
    for (int n; T; --T)
    {
        read(n, mod);
        int res = 0;
        for (int i = 1; i <= n; ++i)
            for (int x = binpow(i, i), t = x, j = 1, k = i; k <= n; ++j, k += i, t = (LL)t * x % mod) if (f[j])
            {
                if (t == 1) res = (f[j] * binpow(n / k, 2) + res) % mod;
                else res = (f[j] * binpow((LL)(binpow(t, n / k + 1) - t) * binpow(t - 1) % mod, 2) + res) % mod;
            }
        write((res + mod) % mod), puts("");
    }
    return 0;
}