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;
}
顺便说下，这题是个三倍经验题。
另外两题是：DIVCNT2 和 DIVCNT3
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！
0 条评论