题意
(sigma_0(i)) 表示 (i) 的约数个数
求
共 (T) 组数据 (Tle10^4,n,kle10^{10})
题解
其实 SPOJ 上还有 divcnt2,divcnt3 ，三倍经验题2333
其实是 min_25 裸题 233
令 (f(x) = sigma_0(x^k)) ，不难发现它是个积性函数，且单点求值较快。
前面 讲过了如何非递归在 (displaystyle O(frac{n^{frac{3}{4}}}{ln n})) 的时间里处理出所有素数的积性函数的前缀和。
现在终于来填合数的部分了 qwq
令 (S(n, i)) 为 (le n) 的所有数 (x) 中，(x) 的最小质因子 (ge P_i) 的 (f(x)) 之和。
接下来我们先算上所有满足条件的质数贡献之和，即 (displaystyle g(n,|P|) - sum_{j = 1}^{i - 1}f(P_j)) 。
对于合数，我们利用积性的性质，直接枚举其最小质因子以及质因子的个数，直接递归计算。
注意在这里形如 (p^k,(p∈P)) 的贡献并没有算进去，所以还要单独加一下。式子的形式如下：
最后我们需要求的就是 (S(n, 1)) 。因为第二维不能逐次除去，状态是不能很好确定的。所以对于非递归来说不太友好，我们递归计算。
如果当前的 (n le 1) 或者 (P_i > n) 那么直接返回 (0) 退出。（注意 (1) 的贡献是最后单独算的）
然后这个直接计算的复杂度似乎也是 (displaystyle O(frac{n^{frac{3}{4}}}{ln n})) 的。（不会证。。）
最后要解决这题的话，只需要知道
对于 (x) 的唯一分解 (x = prod_{i} {p_i}^{{k_i}})
[sigma_0(x) = prod_{i}(k_i + 1) ]
所以就有 (f(p) = k + 1, f(p^e) = ek + 1) 。然后就能解决此题啦。
代码
#include <bits/stdc++.h>
#define For(i, l, r) for (register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for (register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Rep(i, r) for (register int i = (0), i##end = (int)(r); i < i##end; ++i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << (x) << endl
using namespace std;
typedef unsigned long long ll;
template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, T b) { return b > a ? a = b, 1 : 0; }
inline ll read() {
ll x(0), sgn(1); char ch(getchar());
for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;
for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);
return x * sgn;
}
void File() {
#ifdef zjp_shadow
freopen ("34096.in", "r", stdin);
freopen ("34096.out", "w", stdout);
#endif
}
const int N = 1e5 + 1e3;
int prime[N], pcnt; bitset<N> is_prime;
void Linear_Sieve(int maxn) {
is_prime.set();
For (i, 2, maxn) {
if (is_prime[i]) prime[++ pcnt] = i;
for (int j = 1; j <= pcnt && 1ll * i * prime[j] <= maxn; ++ j) {
is_prime[i * prime[j]] = false; if (!(i % prime[j])) break;
}
}
}
int id1[N], id2[N]; ll val[N * 2], res[N * 2], k, d, all;
#define id(x) (x <= d ? id1[x] : id2[all / (x)])
void Min25_Sieve(ll n) {
d = sqrt(n); int cnt = 0;
for (ll i = 1; i <= n; i = n / (n / i) + 1)
val[id(n / i) = ++ cnt] = n / i, res[cnt] = val[cnt] - 1;
for (int i = 1; i <= pcnt && 1ll * prime[i] * prime[i] <= n; ++ i)
for (int j = 1; j <= cnt && 1ll * prime[i] * prime[i] <= val[j]; ++ j)
res[j] -= res[id(val[j] / prime[i])] - (i - 1);
}
ll S(ll n, int cur) {
if (n <= 1 || (ll)prime[cur] > n) return 0;
ll ans = (k + 1) * (res[id(n)] - (cur - 1));
for (int i = cur; i <= pcnt && 1ll * prime[i] * prime[i] <= n; ++ i) {
ll prod = prime[i];
for (int e = 1; prod * prime[i] <= n; ++ e, prod *= prime[i])
ans += (e * k + 1) * S(n / prod, i + 1) + ((e + 1) * k + 1);
}
return ans;
}
int main () {
File();
int cases = read();
Linear_Sieve(1e5);
while (cases --) {
ll n = read(); k = read(); all = n;
Min25_Sieve(n);
printf ("%llu
", S(n, 1) + 1);
}
return 0;
}