HDU 6069 Counting Divisors(多校4)

Problem Description

In mathematics, the function d(n) denotes the number of divisors of positive integer n.

For example, d(12)=6 because 1,2,3,4,6,12 are all 12’s divisors.

In this problem, given l,r and k, your task is to calculate the following thing :

(∑ri=ld(ik))mod998244353

Input

The first line of the input contains an integer T(1≤T≤15), denoting the number of test cases.

In each test case, there are 3 integers l,r,k(1≤l≤r≤1012,r−l≤106,1≤k≤107) .

Output

For each test case, print a single line containing an integer, denoting the answer.

Sample Input

3 1 5 1 1 10 2 1 100 3

Sample Output

10 48 2302

题目大意

求[l,r]区间内每个数k次方的因子个数之和。

解题思路

首先要知道： 1、约数个数定理： 对于一个大于1的正整数n可以分解质因数： n=p1a1∗p2a2∗p3a3∗⋅⋅⋅⋅⋅⋅∗pkak ，则n的正约数的个数就是 f(n)=(a1+1)∗(a2+1)∗(a3+1)∗⋅⋅⋅⋅⋅⋅∗(ak+1) ； 由此定理可得 nk=p1k∗a1∗p2k∗a2∗p3k∗a3∗⋅⋅⋅⋅⋅⋅∗pkk∗ak ，所以 nk 的正约数个数之和为 (k∗a1+1)∗(k∗a2+1)∗(k∗a3+1)∗⋅⋅⋅⋅⋅⋅∗(k∗ak+1) 。 2、埃拉托斯特尼筛法： 要得到自然数n以内的全部素数，必须把不大于 n−−√ 的所有素数的倍数剔除，剩下的就是素数。 由此定理我们便可以得到解题的大致思路，由于l,r的取值范围最大到 1012 ，所以我们可以先用素数筛法打表求出 1012−−−−√=106 内的所有素数，然后枚举每一个素数i，计算每个素数对区间l~r任一数的贡献值，即判断从l~r中的任一数是不是 i 的倍数，若是，则该倍数对应着约数个数定理中的ai(指数)，按照公式求解即可。 将表中每一个素数遍历完之后，若仍有值不为1的情况，根据埃拉托斯特尼定理可得该剩余的数即为素数，且其对应的ai=1，带入公式。 将l~r每个数求得的结果分别相加即为最终答案。

代码实现

#include <iostream> #include<cstring> #include<cstdio> using namespace std; #define maxn 1000006 #define mod 998244353 #define ll long long int prime[maxn],num=0; ll sum[maxn],a[maxn]; bool visit[maxn]; void getprime() { int i; memset(visit,0,sizeof(visit)); for(i=2; i<maxn; i++) { if(!visit[i]) { prime[num++]=i; for(int j=i+i; j<maxn; j+=i) visit[j]=1; } } } int main() { int T; ll l,r,k; scanf("%d",&T); getprime(); while(T--) { ll ans=0; scanf("%lld %lld %lld",&l,&r,&k); for(int i=0;i<=r-l;i++) sum[i]=1,a[i]=i+l; for(int i=0;i<num;i++) { ll t=(l/prime[i]+(l%prime[i]?1:0))*prime[i]; //因为+运算符优先级高于?: 所以三目运算符外必须要有括号 for(ll j=t;j<=r;j+=prime[i]) { int countt=0; while(a[j-l]%prime[i]==0) { countt++; a[j-l]/=prime[i]; } sum[j-l]=(sum[j-l]*(countt*k+1)%mod)%mod; } } for(int i=0;i<=r-l;i++) { if(a[i]!=1) sum[i]=((sum[i]*(k+1))%mod)%mod; ans=(ans+sum[i]%mod)%mod; } printf("%lld\n",ans); } return 0; }