HDU 6069 Counting Divisors (素因子求贡献)

数论 素数 素分解 贡献 HDU 2017多校赛

Description

给定 l​ ， r​ 和 k​ ，计算以下表达式的值。

∑i=lrd(ik)mod998244535 其中 d(n) 为 n 的正因子数量。

Input

第一行给出用例组数T，接下来 T 行，每行给出三个整数l， r 和k。 1⩽l⩽r⩽1012, r−l⩽106, 1⩽k⩽107 。

Output

对于每组测试用例，输出一个整数表示答案。

Sample Input

3 1 5 1 1 10 2 1 100 3

Sample Output

10 48 2302

Solution

易知若 n 的素因子分解为n=pk11pk22⋯pkss，则 d(n)=(k1+1)(k2+1)⋯(ks+1) ， d(nk)=(kk1+1)(kks+1)⋯(kks+1) 。因此要得到 ik 的因子数只需要素因子分解 i 。

一个数n的素因子主要分布在[1,n√]的范围内， [n√,n] 内最多有一个。反证：假设 [n√,n] 有两个素因子 p 和q，则 p×q⩾n ，矛盾。

区间 [l,r]​ 内每个数的素因子，主要分布在 [1,r√]​ 内， [r√,r]​ 内最多有一个。于是线性筛出 [1,r√]​ 范围内的所有质数，枚举每个质数 p​ ，枚举 [l,r]​ 内所有 p​ 的倍数，计算 p​ 对它们的全部贡献。然后枚举 [l,r]​ 内的每个数，如果在 [r√,r]​ 内还有素因子，一并算上。

时间复杂度为 O(∑ri=lΩ(i)) ，其中 Ω(i) 为 i <script id="MathJax-Element-74" type="math/tex">i</script>的素因子数量。

Code

#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; const ll mod = 998244353; const int N = 1e6 + 10; int is_prime[N], prime[N], tot; void get_prime(int n) { for (int i = 1; i <= n; i++) is_prime[i] = true; is_prime[0] = is_prime[1] = false; tot = 0; for (int i = 2; i <= n; i++) { if (is_prime[i]) prime[tot++] = i; for (int j = 0; j < tot && prime[j] * i <= n; j++) { is_prime[prime[j] * i] = false; if (i % prime[j] == 0) break; } } } ll a[N], d[N]; int main() { int T; scanf("%d", &T); get_prime(1e6); while (T--) { ll l, r, k; scanf("%lld%lld%lld", &l, &r, &k); for (ll i = l; i <= r; i++) a[i - l] = i, d[i - l] = 1;; for (int i = 0; i < tot; i++) { ll p = prime[i]; ll t = ceil((double)l / p) * p; for (ll j = t; j <= r; j += p) { int tot = 0; while (a[j - l] % p == 0) tot++, a[j - l] /= p; d[j - l] = d[j - l] * (tot * k % mod + 1) % mod; } } ll ans = 0; for (ll i = l; i <= r; i++) { if (a[i - l] != 1) d[i - l] = d[i - l] * (k + 1) % mod; ans = (ans + d[i - l]) % mod; } printf("%lld\n", ans); } return 0; }

Link

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