Problem

acm.hdu.edu.cn/showproblem.php?pid=6069

Meaning

定义函数d(n) = n 的因子个数。 给定区间 [ l , r ] 和常数 k，求

( ∑i = lrd(ik) ) mod 998244353

Analysis

朴素的想法，先把每一个 i 都质因数分解， i=pe11…penn ，于是 ik 对答案的贡献就是 (e1k+1)(e2k+1)…(enk+1) ，最后答案就是：

( ∑i=lr∏j=1n(ejk+1) ) mod 998244353 就先打一个 106 的素数表（如果有大于 106 的质因子，那么只能有一个，并且指数为 1），然后枚举 [ l , r ] 里的数，对每一个都做一次质数分解、统计答案，超时。 一种优化：对于某个 i，质因子分别为 p1、…、pn ，那么在处理完 ik 的贡献后，可以一并处理掉 (ie1)k、…、(ien)k 的贡献，因为它们只间只有其中一个因式 (ejk+1) 变成 ((ej+1)k+1) 这一个差别，这样就可以少做一些质因数分解（有点像素筛的过程），但还是超时。 可能主要是因为每次质因数分解都要扫一遍质数表，做了很多无用功。 反过来想，不从 i 分解质因子，而是用个数组装下区间[l , r]和它们的贡献（初始为 1），枚举 106 内的质数，对每一个质数 p，在区间内找它的倍数来拆（分解），拆完之后更新这个数的贡献，最后再把贡献求和。

Code

#include <cstdio> #include <cstring> using namespace std; const int N = 1000000, MOD = 998244353; int prime[N+1], top; // prime table void sieve() { top = 0; memset(prime, -1, sizeof prime); for(int i = 2; i <= N; ++i) { if(prime[i]) prime[top++] = i; for(int j = 0; j < top && prime[j] <= N / i; ++j) { prime[i * prime[j]] = 0; if(i % prime[j] == 0) break; } } } long long cntr[N+1]; // 区间内每个数的贡献 long long num[N+1]; // 区间内的数 int main() { sieve(); int T; scanf("%d", &T); while(T--) { long long l, r, k; scanf("%I64d%I64d%I64d", &l, &r, &k); for(int i = 0; i <= r - l; ++i) { num[i] = l + i; cntr[i] = 1; } for(int i = 0, p, beg; i < top; ++i) { p = prime[i]; beg = (p - l % p) % p; // 区间里第一个是p倍数的数的下标 // 枚举 p 的倍数 for(int j = beg, cnt; j <= r - l; j += p) { // 质数分解 for(cnt = 0; num[j] % p == 0; num[j] /= p) ++cnt; // 更新贡献 cntr[j] = cntr[j] * (cnt * k + 1) % MOD; } } // 补上大于 1e6 的质因数的贡献 for(int i = 0; i <= r - l; ++i) if(num[i] > 1) cntr[i] = cntr[i] * (k + 1) % MOD; long long ans = 0; for(int i = 0; i <= r - l; ++i) ans = (ans + cntr[i]) % MOD; printf("%I64d\n", ans); } return 0; }

TLE Code

#include <cstdio> #include <cstring> using namespace std; const int N = 1000000, MOD = 998244353; struct node { int v; // 因子的值 int num; // 因子的指数 } dv[N+10]; // 分解出来的因子 long long prime[N+10], top, d; bool vis[N+10]; // 标记这个数有没有被处理过 void seive(int n) { top = 0; memset(prime, -1, sizeof prime); for(int i = 2; i <= N; ++i) if(prime[i]) { prime[top++] = i; for(int j = i; j <= N; j+=i) prime[j] = 0; } } // 快速幂 long long fpow(long long a, long long b) { long long ans = 1; for( ; b; b >>= 1, a = a * a % MOD) if(b & 1) ans = ans * a % MOD; return ans; } // 逆元 long long inv(long long a) { return fpow(a, MOD - 2); } // 质因数分解 void dvide(long long x) { d = 0; for(int i = 0; i < top && prime[i] * prime[i] <= x; ++i) if(x % prime[i] == 0) { dv[d].v = prime[i]; dv[d].num = 0; while(x % prime[i] == 0) { ++dv[d].num; x /= prime[i]; } ++d; } if(x != 1) { dv[d].v = x; dv[d++].num = 1; } } int main() { int t; scanf("%d", &t); seive(N); while(t--) { long long l, r; int k; scanf("%lld%lld%d", &l, &r, &k); memset(vis, false, sizeof vis); long long ans = 0; for(long long i = l, tmp; i <= r; ++i) { if(vis[i - l]) continue; vis[i - l] = true; dvide(i); // 分解 tmp = 1; // 贡献 for(int j = 0; j < d; ++j) tmp = tmp * (dv[j].num * k + 1) % MOD; ans = (ans + tmp) % MOD; // 顺便处理 i * ej 的贡献 for(int j = 0; j < d && i * dv[j].v <= r; ++j) { if(vis[i * dv[j].v - l]) continue; vis[i * dv[j].v - l] = true; ans = (ans + tmp + (tmp * inv(dv[j].num * k + 1) % MOD * k)) % MOD; } } printf("%lld\n", ans % MOD); } return 0; }