[2017 Multi-University Training Contest - Team 4] HDU 6069 Counting Divisors
题目链接:
HDU 6069
题目大意：
给定
l,r,k
定义
d(x)
为
x
因子的个数, 求：
(∑i=lrd(ik))mod998244353
数据范围：
l,r,k(1≤l≤r≤1012,r−l≤106,1≤k≤107)
解题思路：
我们将
x
分解质因数x=px11∗px22∗px22... 那么
x
因子的个数为 (x1 1)∗(x2 1)∗(x3 1)... 因此， 我们可以先线性筛出
1到1012−−−−√
的素数，再把从
l到r√
对于每一个质数能整除谁筛出来， 最后大于
r√
最多只有一个， 单独算一下就好 因为是
k
次幂, 所以答案应对于每个x1都应该乘以
k
<script type="math/tex" id="MathJax-Element-19">k</script>。
代码：
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
typedef long long LL;
const int MaxN =
1e6;
const int pt =
998244353;
int T;
LL l, r, k;
int prime[MaxN +
5];
LL num[MaxN +
5], sum[MaxN +
5];
int pcnt;
bool vis[MaxN +
5];
void getprime(){
for(
int i =
2; i <= MaxN; i++){
if(!vis[i]) prime[++pcnt] = i;
for(LL j =
1; j <= pcnt && i * prime[j] <= MaxN; j++){
vis[i * prime[j]] =
true;
if(i % prime[j] ==
0)
break;
}
}
}
int main(){
scanf(
"%d", &T);
getprime();
while(T--){
scanf(
"%lld %lld %lld", &l, &r, &k);
for(
int i =
1; i <= r - l +
1; i++) num[i] = l + i -
1, sum[i] =
1;
LL tmp =
sqrt(r);
for(
int i =
1; i <= pcnt; i++){
LL x = l, p = prime[i];
if(p > tmp)
break;
if(x % p !=
0) x = x + p - x % p;
while(x <= r){
int pos = x - l +
1;
LL cnt =
0;
while(num[pos] % p ==
0) cnt++, num[pos] /= p;
sum[pos] = sum[pos] * (cnt * k % pt +
1) % pt;
x += p;
}
}
LL ans =
0;
for(
int i =
1; i <= r - l +
1; i++)
if(num[i] >
1)
sum[i] = sum[i] * (k +
1) % pt;
for(
int i =
1; i <= r - l +
1; i++) ans = (ans + sum[i]) % pt;
printf(
"%lld\n", ans);
}
return 0;
}
标签： HDU 分解质因数 多校
