# 1. 题目

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

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

# 2. 题解

/*
* DIVCNTK.cpp
* This file is part of DIVCNTK
*
* Copyright (C) 2018 - xzy
*
* DIVCNTK is free software; you can redistribute it and/or modify
* 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 的代码：

/*
* DIVCNT2.cpp
* This file is part of DIVCNT2
*
* Copyright (C) 2018 - xzy
*
* DIVCNT2 is free software; you can redistribute it and/or modify
* 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
* 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;
}