hdu--6069--Counting Divisors

àì夳堔傛蜴生んèń 2022-06-10 01:37 128阅读 0赞

# Counting Divisors #

**Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)  
Total Submission(s): 2947    Accepted Submission(s): 1084**

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

Source

[2017 Multi-University Training Contest - Team 4][]

题意：d(i)表示i的因子个数；给出l,r,k。求出(∑i=lrd(ik))mod998244353

解题思路：根据约数个数定理得出：n=p1^c1\*p2^c2\*.....\*pn^cn;

可得：d(n)=(c1+1)\*(c2+1)\*.....\*(cn+1);

进一步：d(n^k)=(c1\*k+1)\*(c2\*k+1)\*.....\*(cn\*k+1);

d(n)里的n取值范围为1--10^12;要判断n是不是素数，只需要打1--10^6的素数表。

如果n是素数，那么他的贡献为（k+1），如果n不是素数，就用表内的素数进行分解；

具体做法是遍历已经打印好的素数表prime\[maxn\],另外开一个数组a，存放l到r，对应的下标为0到r-l;

遍历prime\[i\]时，先找到a数组内第一个能整除prime\[i\]的元素a\[j\],并用prime\[i\]对它进行分解，直到除不尽。

此后，每次a的下标加prime\[i\]个，做到消除a内以prime\[i\]为因子的数。

最后只要 a\[i\]不等于1，则其一定剩下的是一个大于 10^6的素数了。

代码：

C++ Code

<table style="width:100%; font-family:'Consolas','Courier New'; font-size:12px; vertical-align:text-top; line-height:15px"> 
 <tbody> 
 <tr> 
 <td style="color:#008284; background-color:#e3e3e3; vertical-align:text-top"> 
 <div style="margin:7px; text-align:right; white-space:nowrap">
 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 32 
 33 
 34 
 35 
 36 
 37 
 38 
 39 
 40 
 41 
 42 
 43 
 44 
 45 
 46 
 47 
 48 
 49 
 50 
 51 
 52 
 53 
 54 
 55 
 56 
 57 
 58 
 59 
 60 
 61 
 62 
 63 
 64 
 65 
 66 
 67 
 68 
 69 
 70 
 71 
 72 
 73 
 74 
 75 
 76 
 77 
 
 </div> </td> 
 <td style="background-color:#008284; padding:1px"> 
 <div style="border:1px #008284 solid"></div> </td> 
 <td style="background-color:rgb(239,239,239); width:100%; vertical-align:text-top"> 
 <div style="margin:7px"> 
 #include&nbsp;&lt;bits/stdc++.h&gt; 
 
 using&nbsp; 
 namespace&nbsp;std; 
 
 typedef&nbsp; 
 long&nbsp; 
 long&nbsp;LL; 
 
 const&nbsp; 
 int&nbsp;mod&nbsp;=&nbsp; 
 998244353; 
 
 const&nbsp; 
 int&nbsp;maxn&nbsp;=&nbsp; 
 1000009; 
 
 bool&nbsp;Isprime[maxn];&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///素数表1 LL&nbsp;prime[maxn];&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///素数表2 LL&nbsp;a1[maxn],&nbsp;sum[maxn]; 
 
 int&nbsp;cnt; 
 LL&nbsp;l,&nbsp;r,&nbsp;k; 
 
 void&nbsp;Prime() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 ///打印素数表，Isprime[&nbsp;]和prime[&nbsp;]； &nbsp;&nbsp;&nbsp;&nbsp;cnt&nbsp;=&nbsp; 
 0; 
 &nbsp;&nbsp;&nbsp;&nbsp;memset(Isprime,&nbsp; 
 true,&nbsp; 
 sizeof(Isprime)); 
 &nbsp;&nbsp;&nbsp;&nbsp;Isprime[ 
 1]&nbsp;=&nbsp; 
 false; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i&nbsp;=&nbsp; 
 2&nbsp;;&nbsp;i&nbsp;&lt;&nbsp;maxn&nbsp;;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(Isprime[i]) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;prime[cnt++]&nbsp;=&nbsp;i; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;j&nbsp;=&nbsp; 
 2&nbsp;;&nbsp;i&nbsp;*&nbsp;j&nbsp;&lt;&nbsp;maxn&nbsp;;&nbsp;j++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Isprime[i&nbsp;*&nbsp;j]&nbsp;=&nbsp; 
 false; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 } 
 
 
 int&nbsp;main() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp;Prime(); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;t; 
 &nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d",&nbsp;&amp;t); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 while(t--) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%lld%lld%lld",&nbsp;&amp;l,&nbsp;&amp;r,&nbsp;&amp;k); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i&nbsp;=&nbsp; 
 0;&nbsp;i&nbsp;&lt;=&nbsp;r&nbsp;-&nbsp;l;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sum[i]&nbsp;=&nbsp; 
 1;&nbsp; 
 ///sum是要做乘法的，初值为1 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a1[i]&nbsp;=&nbsp;i&nbsp;+&nbsp;l;&nbsp; 
 ///对应存储l--r的值； &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i&nbsp;=&nbsp; 
 0;&nbsp;i&nbsp;&lt;&nbsp;cnt;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;x; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(l&nbsp;%&nbsp;prime[i]&nbsp;!=&nbsp; 
 0) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x&nbsp;=&nbsp; 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 else&nbsp; 
 if(l&nbsp;%&nbsp;prime[i]&nbsp;==&nbsp; 
 0) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x&nbsp;=&nbsp; 
 0; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;LL&nbsp;fir&nbsp;=&nbsp;(l&nbsp;/&nbsp;prime[i]&nbsp;+&nbsp;x)&nbsp;*&nbsp;prime[i];&nbsp; 
 ///fir是从l开始第一个能整除prime[i]的 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for(LL&nbsp;j&nbsp;=&nbsp;fir;&nbsp;j&nbsp;&lt;=&nbsp;r;&nbsp;j&nbsp;+=&nbsp;prime[i])&nbsp; 
 ///每个j都能整除prime[i] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;LL&nbsp;res&nbsp;=&nbsp; 
 0; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 while(a1[j&nbsp;-&nbsp;l]&nbsp;%&nbsp;prime[i]&nbsp;==&nbsp; 
 0) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res++; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a1[j&nbsp;-&nbsp;l]&nbsp;/=&nbsp;prime[i]; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 ///一直除下去,让数变小，找到prime[i]的幂值 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sum[j&nbsp;-&nbsp;l]&nbsp;=&nbsp;(sum[j&nbsp;-&nbsp;l]&nbsp;*&nbsp;((res&nbsp;*&nbsp;k&nbsp;+&nbsp; 
 1)&nbsp;%&nbsp;mod))&nbsp;%&nbsp;mod;&nbsp; 
 ///sum[j-l]乘一下，取模 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;LL&nbsp;ans&nbsp;=&nbsp; 
 0; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i&nbsp;=&nbsp; 
 0;&nbsp;i&nbsp;&lt;=&nbsp;r&nbsp;-&nbsp;l;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(a1[i]&nbsp;!=&nbsp; 
 1) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sum[i]&nbsp;=&nbsp;(sum[i]&nbsp;*&nbsp;(k&nbsp;+&nbsp; 
 1))&nbsp;%&nbsp;mod;&nbsp; 
 ///经过一系列除法没除到1，说明1e6内的素数分解不了，那么它就是一个大素数 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ans&nbsp;=&nbsp;(ans&nbsp;+&nbsp;sum[i])&nbsp;%&nbsp;mod; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "%lld\n",&nbsp;ans); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp; 
 0; 
 } 
 
 </div> </td> 
 </tr> 
 </tbody> 
</table>

[2017 Multi-University Training Contest - Team 4]: http://acm.hdu.edu.cn/search.php?field=problem&key=2017+Multi-University+Training+Contest+-+Team+4&source=1&searchmode=source