1. 题目

传送门= ̄ω ̄=

题意:

设$\sigma_0(a)$为$a$的约数个数

设:

$$f(a)=\sigma_0(a^3)$$

求:

$$\sum _ {i=1} ^ {n} f(i)$$

2. 题解

不难发现$f(x)$是个积性函数。

求前缀和的话直接上扩展埃氏筛即可。

扩展埃氏筛不做详细描述,也许以后会发博客讲。

代码:

/*
 * DIVCNTK.cpp
 * This file is part of DIVCNTK
 *
 * Copyright (C) 2018 - xzy
 *
 * DIVCNTK is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * DIVCNTK is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with DIVCNTK. If not, see <http://www.gnu.org/licenses/>.
 */


#pragma GCC optimize("Ofast")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC target("avx","sse4","sse4.1","sse4.2","ssse3")
#pragma GCC target("f16c")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC diagnostic error "-std=c++14"

#include <bits/stdc++.h>

#define SQS (100005)

using namespace std;

typedef unsigned long long ULL;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

ULL sqx, pre[SQS], suf[SQS], prm[SQS], pcnt;

int T;

void E_Sieve(ULL x)
{
    if (x <= 1) return;
    sqx = sqrt(x);
    for (ULL i = 1; i <= sqx; i += 1)
        pre[i] = i - 1, suf[i] = x / i - 1;
    for (ULL p = 2; p <= sqx; p += 1)
    {
        if (pre[p] == pre[p - 1]) continue;
        prm[++pcnt] = p;
        ULL t = pre[p - 1];
        for (ULL i = 1; i <= sqx / p; i += 1)
            suf[i] -= suf[i * p] - t;
        for (ULL i = sqx / p + 1; i <= min(sqx, x / p / p); i += 1)
            suf[i] -= pre[x / i / p] - t;
        for (ULL i = sqx; i >= p * p; i -= 1)
            pre[i] -= pre[i / p] - t;
    }
}

ULL n, k, ans;

void Min25(ULL cnt, ULL res, ULL rem)
{
    ULL t = (rem <= sqx ? pre[rem] : suf[n / rem]);
    ans += res * (k + 1) * (t - pre[prm[cnt - 1]]);
    for (ULL i = cnt; i <= pcnt; i += 1)
    {
        if (rem < prm[i] * prm[i]) break;
        for (ULL j = prm[i], e = 1; j <= rem; j *= prm[i], e += 1)
        {
            if (j * prm[i] < rem) Min25(i + 1, (k * e + 1) * res, rem / j);
            if (e > 1) ans += (k * e + 1) * res;
        }
    }
}

int main(int argc, char const* argv[])
{
    IN(T);
    while (T--)
    {
        IN(n), IN(k), ans = 1, pcnt = 0;
        E_Sieve(n), Min25(1, 1, n), printf("%llu\n", ans);
    }
    return 0;
}

顺便说下,这题是个三倍经验题

另外两题是:DIVCNT2DIVCNT3

DIVCNT2的代码:

/*
 * DIVCNT2.cpp
 * This file is part of DIVCNT2
 *
 * Copyright (C) 2018 - xzy
 *
 * DIVCNT2 is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * DIVCNT2 is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with DIVCNT2. If not, see <http://www.gnu.org/licenses/>.
 */


#pragma GCC optimize("Ofast")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC target("avx","sse4","sse4.1","sse4.2","ssse3")
#pragma GCC target("f16c")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC diagnostic error "-std=c++14"

#include <bits/stdc++.h>

#define SQS (1000005)

using namespace std;

typedef unsigned long long ULL;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

ULL sqx, pre[SQS], suf[SQS], prm[SQS], pcnt;

int T;

void E_Sieve(ULL x)
{
    if (x <= 1) return;
    sqx = sqrt(x);
    for (ULL i = 1; i <= sqx; i += 1)
        pre[i] = i - 1, suf[i] = x / i - 1;
    for (ULL p = 2; p <= sqx; p += 1)
    {
        if (pre[p] == pre[p - 1]) continue;
        prm[++pcnt] = p;
        ULL t = pre[p - 1];
        for (ULL i = 1; i <= sqx / p; i += 1)
            suf[i] -= suf[i * p] - t;
        for (ULL i = sqx / p + 1; i <= min(sqx, x / p / p); i += 1)
            suf[i] -= pre[x / i / p] - t;
        for (ULL i = sqx; i >= p * p; i -= 1)
            pre[i] -= pre[i / p] - t;
    }
}

ULL n, k, ans;

void Min25(ULL cnt, ULL res, ULL rem)
{
    ULL t = (rem <= sqx ? pre[rem] : suf[n / rem]);
    ans += res * (k + 1) * (t - pre[prm[cnt - 1]]);
    for (ULL i = cnt; i <= pcnt; i += 1)
    {
        if (rem < prm[i] * prm[i]) break;
        for (ULL j = prm[i], e = 1; j <= rem; j *= prm[i], e += 1)
        {
            if (j * prm[i] < rem) Min25(i + 1, (k * e + 1) * res, rem / j);
            if (e > 1) ans += (k * e + 1) * res;
        }
    }
}

int main(int argc, char const* argv[])
{
    IN(T);
    while (T--)
    {
        IN(n), k = 2, ans = 1, pcnt = 0;
        E_Sieve(n), Min25(1, 1, n), printf("%llu\n", ans);
    }
    return 0;
}

DIVCNT3的代码:

/*
 * DIVCNT3.cpp
 * This file is part of DIVCNT3
 *
 * Copyright (C) 2018 - xzy
 *
 * DIVCNT3 is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * DIVCNT3 is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with DIVCNT3. If not, see <http://www.gnu.org/licenses/>.
 */


#pragma GCC optimize("Ofast")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC target("avx","sse4","sse4.1","sse4.2","ssse3")
#pragma GCC target("f16c")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC diagnostic error "-std=c++14"

#include <bits/stdc++.h>

#define SQS (400005)

using namespace std;

typedef unsigned long long ULL;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

ULL sqx, pre[SQS], suf[SQS], prm[SQS], pcnt;

int T;

void E_Sieve(ULL x)
{
    if (x <= 1) return;
    sqx = sqrt(x);
    for (ULL i = 1; i <= sqx; i += 1)
        pre[i] = i - 1, suf[i] = x / i - 1;
    for (ULL p = 2; p <= sqx; p += 1)
    {
        if (pre[p] == pre[p - 1]) continue;
        prm[++pcnt] = p;
        ULL t = pre[p - 1];
        for (ULL i = 1; i <= sqx / p; i += 1)
            suf[i] -= suf[i * p] - t;
        for (ULL i = sqx / p + 1; i <= min(sqx, x / p / p); i += 1)
            suf[i] -= pre[x / i / p] - t;
        for (ULL i = sqx; i >= p * p; i -= 1)
            pre[i] -= pre[i / p] - t;
    }
}

ULL n, k, ans;

void Min25(ULL cnt, ULL res, ULL rem)
{
    ULL t = (rem <= sqx ? pre[rem] : suf[n / rem]);
    ans += res * (k + 1) * (t - pre[prm[cnt - 1]]);
    for (ULL i = cnt; i <= pcnt; i += 1)
    {
        if (rem < prm[i] * prm[i]) break;
        for (ULL j = prm[i], e = 1; j <= rem; j *= prm[i], e += 1)
        {
            if (j * prm[i] < rem) Min25(i + 1, (k * e + 1) * res, rem / j);
            if (e > 1) ans += (k * e + 1) * res;
        }
    }
}

int main(int argc, char const* argv[])
{
    IN(T);
    while (T--)
    {
        IN(n), k = 3, ans = 1, pcnt = 0;
        E_Sieve(n), Min25(1, 1, n), printf("%llu\n", ans);
    }
    return 0;
}

至于DIVCNT1的话,如果您用扩展埃氏筛做,想AC得跑2.18227293407481379715天,SOUNDS GREAT!

分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *