ICPC南京网络赛E.Ksum

题意:

$$f(k)=\sum_{i_{1}=1}^{n}\sum_{i_{2}=1}^{n}\sum_{i_{3}=1}^{n} ...\sum_{i_{k}=1}^{n}(gcd(i_{1},i_{2},i_{3}..i_{k}))^2$$ $$求g(n)=\sum_{k=2}^{n}f(k)$$

化简开始

$$f(k)=\sum_{x=1}^{n}x^2\sum_{i_{1}=1}^{n}\sum_{i_{2}=1}^{n}\sum_{i_{3}=1}^{n} ...\sum_{i_{k}=1}^{n}[gcd(i_{1},i_{2},i_{3}..i_{k})=x]$$ $$\sum_{x=1}^{n}x^2\sum_{i_{1}=1}^{\frac{n}{x}}\sum_{i_{2}=1}^{\frac{n}{x}}\sum_{i_{3}=1}^{\frac{n}{x}} ...\sum_{i_{k}=1}^{\frac{n}{x}}[gcd(i_{1},i_{2},i_{3}..i_{k})=1]$$

莫比乌斯反演

$$\sum_{x=1}^{n}x^2\sum_{d=1}^{\frac{n}{d}}x^2\mu(d)(\frac{n}{xd})^k$$

令$T=xd$

$$\sum_{T=1}^{n}(\frac{n}{T})^k\sum_{d|T}^{}(\frac{T}{d})^2\mu(d)$$ $$g(n)=\sum_{k=2}^{n}\sum_{T=1}^{n}(\frac{n}{T})^k\sum_{d|T}^{}(\frac{T}{d})^2\mu(d)$$ $$\sum_{T=1}^{n} (\sum_{k=1}^{n}(\frac{n}{T})^k)\sum_{d|T}^{}(\frac{T}{d})^2\mu(d)$$

前面分块即可
然后需要求后面那一块，就设

$$H(n)=\sum_{T=1}^{n}\sum_{d|T}^{}(\frac{T}{d})^2\mu(d)$$ $$id^2*(\mu*I)=id^2 (注意id^2!=id*id，所以不变成id*\phi )显然\sum_{d|T}^{}(\frac{T}{d})^2 !=\sum_{d|T}^{}(\frac{T}{d})(d)$$

杜教筛

$$H(n)=\sum_{i=1}^{n} i^2 -\sum_{i=1}^{n} H(\frac{n}{i})$$

又可以在一顿推导后

$$h(T)=\sum_{d|T}^{}(\frac{T}{d})^2\mu(d)=T^2\prod_{p|T}(1-\frac{1}{p^2})$$

就可以线性筛递推

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N = 5e6 + 10;
const int mod = 1e9 + 7;
typedef long long ll;

bool notprime[N];
int prime[N], cnt;
int sumf[N];
int f[N];
unordered_map<int, int> v;
int addmod(ll x, ll y)
{
    if (y < 0)
        y += mod;
    if (x + y >= mod)
        x -= mod;
    return x + y;
}
int qpow(int a, int x, int mo)
{
    int res = 1;
    while (x)
    {
        if (x & 1)
            res = 1ll * res * a % mo;
        a = 1ll * a * a % mo;
        x >>= 1;
    }
    return res;
}
void mublus()
{
    f[1] = 1;
    for (int i = 2; i < N; i++)
    {
        if (!notprime[i])
        {
            f[i] = (1ll * i * i - 1) % mod;
            prime[++cnt] = i;
        }
        for (int j = 1; j <= cnt && prime[j] * i < N; j++)
        {
            notprime[prime[j] * i] = true;
            if (i % prime[j])
            {
                f[i * prime[j]] = 1ll * f[i] * (1ll * prime[j] * prime[j] % mod - 1) % mod;
            }
            else
            {
                f[i * prime[j]] = 1ll * f[i] * prime[j] % mod * prime[j] % mod;
                break;
            }
        }
    }
    for (int i = 1; i < N; i++)
        sumf[i] = addmod(sumf[i - 1], f[i]);
}
int k, kk, inv6;
int getsum(int x)
{
    if (x == 1)
        return kk - 1;
    return 1ll * x * addmod(qpow(x, k, mod), -x) % mod * qpow(x - 1, mod - 2, mod) % mod;
}
int getsumx2(int x)
{
    return 1ll * x * (x + 1) % mod * (2 * x + 1) % mod * inv6 % mod;
}
int getf(int x)
{
    if (x < N)
        return sumf[x];
    if (v[x])
        return v[x];
    int ans = getsumx2(x);
    for (int i = 2, j; i <= x; i = j + 1)
    {
        j = x / (x / i);
        ans = addmod(ans, -(1ll * (j - i + 1) * getf(x / i) % mod));
    }
    return v[x] = ans;
}

int n, T;
char str[N];
int main()
{
    mublus();
    inv6 = qpow(6, mod - 2, mod);
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        scanf("%s", str);

        int ans = 0;
        int len = strlen(str);
        int p = mod - 1;
        k = 0;
        kk = 0;
        for (int i = 0; i < len; i++)
        {
            k = addmod(1ll * k * 10 % p, str[i] - '0');
            kk = addmod(1ll * kk * 10 % mod, str[i] - '0');
        }
        //cout << getf(3) << endl;
        for (int i = 1, j; i <= n; i = j + 1)
        {
            j = n / (n / i);
            //cout << n / i << " " << getsum(n / i) << endl;
            ans = addmod(ans, 1ll * addmod(getf(j), -getf(i - 1)) * getsum(n / i) % mod);
        }
        cout << ans << endl;
    }
}