题目链接
赛时没有做出来是我的锅，各种骚操作都没过，想到大数分解上去了，其实本题没这个必要。 题意很简单， 求区间[l, r]内每个数的k次方的所有因子个数。
转载请注明出处，谢谢配合。
这里需要知道一点前导知识： 对任意一个自然数都可以唯一分解为: n=pα11⋅pα22⋯pαss 其中 pi 为素数。
数n的因子个数函数： τ(n)=∏si=0(αi+1) 其中 αi 为上述分解中 pi 的幂。本题中的 k 方很好处理，只要每个 α 都乘一下 k 就可以了
积性函数 f(x) : 如果自然数 x,y 互质， 即 gcd(x,y)=1 ， 则有 f(xy)=f(x)∗f(y)
因子个数函数就是积性函数, 这个性质很重要，本题也是基于这个性质优化的。
思路： 由于数据范围在 1012 以内，故只需要筛 106 以内的素数即可，然后枚举筛得的素数，求每一个素数对区间中的数不妨设为 x 的贡献度，为什么可以这做？上述提到 τ 函数是积性函数，又不同的素数一定是互质的，所以每个素数对 x 的贡献度彼此不影响， 所有我们先枚举每一个素数 pi，因为如果 pi 对 x 有贡献度的话，那么 x 一定是 pi 的倍数，所以我们类似分块的思想，在区间 [l,r] 中以 pi 为间隔遍历， 这样就保证遍历的数一定是 pi 的倍数，所以 pi 对遍历中每个数有贡献度，把贡献度都求出来并存储就能得到所遍历的这些数中其因子 pi 对它们的贡献度了。 x 的不同的素因子对其的贡献度不同，但是只要乘在一起就是最后 x 对总答案 ans 的贡献了， 故数组 num[i] 保存区间中第 i 个数对总答案的贡献度，并用 f[i] 记录第 i 个数被pi “贡献完之后（分解）剩余的值”，最后只要 f[i] 不等于1，则其一定剩下的是一个大于 106 的素数了，而这样的素数也最多只有一个。
代码如下:
/* * HDU 6069 * Time: 2745 ms. * tau(n): total number of factors of n, function tao(n) is multiplicative. * tau(n) = product_(i = 0)^s alpha_i + 1 */ #include <bits/stdc++.h> using namespace std; const long long mod = 998244353; const int MAXN = 1 << 20; int prime[MAXN]; bool isp[MAXN]; int pcnt = 0; void getPrime(int num) { memset(prime, 0, sizeof prime); memset(isp, true, sizeof isp); pcnt = 0; for(int i = 2; i <= num; ++i) { if(isp[i] == true) { prime[pcnt++] = i; } for(int j = 0; j < pcnt && i * prime[j] <= num; ++j) { isp[i * prime[j]] = false; if(i % prime[j] == 0) { break; } } } } long long num[MAXN], f[MAXN]; long long Ceil(long long nume, long long deno) { return (nume + deno - 1) / deno; } int main() { #ifdef LOCAL freopen("data.in", "r", stdin); freopen("data.out", "w", stdout); #endif getPrime(1000000); int T; scanf("%d", &T); long long l, r, k; while(T--) { scanf("%lld %lld %lld", &l, &r, &k); long long ans = 0; if(l == 1) { ans++, l++; } long long len = r - l; for(long long i = 0; i <= len; ++i) { f[i] = i + l; num[i] = 1; } for(int i = 0; i < pcnt && prime[i] * prime[i] <= r; ++i) { // enum at first multiple of prime[i] in range [l, r] long long x = Ceil(l, prime[i]) * prime[i]; for(long long j = x; j <= r; j += prime[i]) { long long cnt = 0; if(f[j - l] % prime[i] == 0) { while(f[j - l] % prime[i] == 0) { cnt++; f[j - l] /= prime[i]; } } // prime[i]'s contribution to number (j + l) num[j - l] = num[j - l] * (k * cnt + 1) % mod; } } for(int i = 0; i <= len; ++i) { if(f[i] == 1) { ans = (ans + num[i]) % mod; } else { // number f[i] is a prime now, k + 1 is the contibution of prime f[i] to previous f[i] ans = (ans + num[i] * (k + 1) % mod) % mod; } } printf("%lld\n", ans); } return 0; }