HDU-6069 Counting Divisors - 2017 Multi-University Training Contest - Team 4(分解质因子区间筛法)
题意：
给定一个区间[L, R]，求区间所有数的d(i^k)并求和。其中d(i)表示i^k的所有因子个数。mod: 998244353，1 <= L,R <= 1e12, R-L <= 1e6, 1 <= k <= 1e7.
思路：
设n = p1^c1*p2^c2...pm^cm
分析可得d(n^k) = (k*c1 + 1)*(k*c2 + 1)...(k*cm + 1)。
思路更像是求一个数所有素因子极其次幂的逆向思维。实际上是利用了区间素数筛的思想。
所以枚举不超过sqrt(R)的所有质数p，再枚举区间[L, R]中所有p的倍数，将它们通过p分解质因数，最后分解完不超过sqrt(R)的所有质数后，区间内的数剩下的值如果不为1则此质因子就是超过sqrt(R)的质数，且其次幂为1个。
代码：
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const LL mod = 998244353;
const int N = 1e6;
const int maxn = 1e6+5;
int isprime[maxn], prime[maxn], len;
LL ans[maxn], num[maxn];
LL L, R, K;
inline void prime_init()
{
len = 0;
memset(isprime, 0, sizeof isprime);
for(int i = 2; i <= N; ++i)
if(!isprime[i])
{
prime[++len] = i;
if(i > sqrt(N)) continue;
for(int j = i*i; j <= N; j+=i)
isprime[j] = 1;
}
}
LL solve()
{
LL fuck = 0;
int UP = R-L+1;
for(int i = 1; i <= UP; ++i)
{
ans[i] = 1;
num[i] = L+i-1;
}
for(int i = 1; i <= len; ++i)
{
if(1ll*prime[i]*prime[i] > R) break;
LL star = ((L-1)/prime[i]+1)*prime[i];//定位第一个在[L,R]区间内为质数倍数的值
for(int id = star-L+1; id <= UP; id+=prime[i])
{
int cnt = 0;
while(num[id]%prime[i] == 0)
{
++cnt;
num[id] /= prime[i];
}
ans[id] = ans[id]*(K*cnt%mod+1)%mod;
}
}
for(int i = 1; i <= UP; ++i)
if(num[i] != 1) ans[i] = ans[i]*(K+1)%mod;
for(int i = 1; i <= UP; ++i) fuck = (fuck+ans[i])%mod;
return fuck;
}
int main()
{
//freopen("in.txt", "r", stdin);
prime_init();
int t;
scanf("%d", &t);
while(t--)
{
scanf("%lld %lld %lld", &L, &R, &K);
printf("%lld\n", solve());
}
return 0;
}
继续加油~