17暑假多校联赛4.3 HDU 6069 Counting Divisors

Counting Divisors

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)  

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 : (∑i=lrd(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

  题目网址：http://acm.hdu.edu.cn/showproblem.php?pid=6069  

分析

题意： T 组测试数据，每组给出 l,r,k ，计算 l 到 r 每个数 k 次方的因子个数，并求和 可以推出规律：质数的 k 次方的因子个数为 k+1 比如求整数 a 的 k 次方的因子个数： 如果 a=6,k=2 ，则 36 的因子有 1,2,3,4,6,9,12,18,36 总共 9 个 如果将 6 分解质因子， 6=2*3 2,3 都是质数，所以 6 的平方的因子数为 (k+1)*(k+1) ，即 3*3=9 可以得出规律：如果 a 分解质因子为 a=p[1]^x*p[2]^y*p[3]^z （其中 p[1],p[2],p[3] 均为素数），则 a 的 k 次方的因子个数为： (x*k+1)*(y*k+1)*(z*k+1) （ a 的 k 次方分解质因子为 a^k=p[1]^(x*k)*p[2]^(y*k)*p[3]^(z*k) ） 所以可以将 l 到 r 每个数分解质因子，并记录每个质因子出现的次数，然后根据上面的规律计算出每个数 k 次方的因子个数，求和即可 由于数值比较大，这道题很容易时间超限，所以要注意求解的方法，还要不断取模  

代码

#include <bits/stdc++.h> using namespace std; typedef long long ll; using namespace std; const int maxn=1e6+10; const int mod=998244353; int tot,t; ll l,r,k,ans,cnt[maxn],q[maxn],primes[maxn]; ///cnt存放d(i^k)的值，q存放区间每个对应位置的数值 bool vis[maxn]; void init()///素数打表 { for(int i=2; i<maxn; i++) { if(!vis[i])///如果没有被标记就存入素数数组 primes[tot++]=i; for(int j=0; j<tot; j++)///将素数i和他的倍数都标记 { int k=i*primes[j]; if(k>maxn)break; vis[k]=1; } } } int main() { scanf("%d",&t); init(); while(t--) { scanf("%lld%lld%lld",&l,&r,&k); ans=0; if(l==1) ans++,l++; ///1的多少次幂都是1，d(1)等于1 ///所以如果左边界是1，直接将ans加1，把左边界移到2 for(ll i=0; i<=r-l; i++) cnt[i]=1,q[i]=l+i; ///将l到r对应位置的数值存入q，给cnt数组赋初值为1 for(ll i=0; primes[i]*primes[i]<=r; i++) { ll j=l/primes[i]+(l%primes[i]!=0); ///i和j来控制primes[i]*j在给定区间内 for( j=j*primes[i]; j<=r; j+=primes[i]) { ll tmp=0; while(q[j-l]%primes[i]==0) q[j-l]/=primes[i],tmp++; ///计算q[j-l]的因数中包含多少个primes[i]，存到tmp中 (cnt[j-l]*=(tmp*k)%mod+1)%=mod; ///将因子数存入cnt[j-l] } } for(ll i=0; i<=r-l; i++) { if(q[i]!=1) ans+=((k+1)*cnt[i])%mod; ///q[i]不为1，说明q[i]的初值是l到r内的素数或其倍数 ///由于前面已经控制了primes[i]*primes[i]<=r ///所以倍数在前边已经计算出了并将其因子数存给了cnt[i] ///因此，只用乘上k+1即可 else ans+=cnt[i]; ans%=mod; } printf("%lld\n",ans); } }