Counting Divisors

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 1996 Accepted Submission(s): 728

Problem Description

In mathematics, the function

d(n) denotes the number of divisors of positive integer

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 :

(\sum i = l r d (i k)) mod 998244353

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

题意：求l到r中所有数的k次方的因数个数之和。

题解：

设 $n=p_1^{c_1}p_2^{c_2}...p_m^{c_m}$ ，则 $d(n^k)=(kc_1+1)(kc_2+1)...(kc_m+1)$ 因为区间长度不超过1e6枚举不超过

r√ 的所有质数

p，再枚举区间

[l,r]中所有

的倍数，将其分解质因数，最后剩下的部分就是超过

r√

的质数，只可能是

个或

个，进行特判一下，将其加上就好了。

注意：这里分解的时候不是把每一个数逐一进行分解，而是类似于区间两次筛，每一次枚举素数的倍数，然后整段的去筛计算素数的指数，相当于每次找len/2,len/3,len/4...len/n次，以节约时间，与的思路有异曲同工之妙。

写的时候傻逼了，把

for (int j = 2 * i; j < maxn; j += i) not_prime[j] = 1;

的not_prime[j] = 1写成了not_prime[i] = 1，T了一万年 (T＿T)

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #define INF 0x3f3f3f3f#define ms(x,y) memset(x,y,sizeof(x))using namespace std;typedef long long ll;const double pi = acos(-1.0);const double eps = 1e-8;const int mod = 998244353;const int maxn = 1e6 + 10;ll prime[maxn]; //记录素数ll l, r, k;ll d[maxn]; //记录这个数的质因数数量ll ans[maxn]; //记录这个数是否可以被完全分解质因数bool not_prime[maxn];int cnt = 0; //素数的个数void getPrime() //埃氏筛法得到1e6内的素数{ not_prime[0] = not_prime[1] = 1; for (int i = 2; i < maxn; i++) { if (!not_prime[i]) { prime[cnt++] = i; for (int j = 2 * i; j < maxn; j += i) not_prime[j] = 1; } }}void solve(){ for (int i = 0; i < cnt; i++) //枚举素数 { ll tmp = (l + prime[i] - 1) / prime[i] * prime[i]; //利用自动取整【(l + prime[i] - 1) / prime[i]】得到l到r的最小的prime[i]的倍数，乘prime[i]得到这个数 while (tmp <= r) { ll cnt = 0; //记录指数是多少 while (ans[tmp - l] % prime[i] == 0) { cnt++; ans[tmp - l] /= prime[i]; } d[tmp - l] = (d[tmp - l] * (k*cnt + 1)) % mod; tmp += prime[i]; //枚举下一倍数 } } ll res = 0; for (ll i = l; i <= r; i++) { if (ans[i - l] == 1) res = (res + d[i - l]) % mod; //如果ans结果为1则证明可以完全分解，直接加上结果即可 else res = (res + d[i - l] * (k + 1)) % mod; //否则表示还有素数且素数指数为1，再乘以1*k+1即可 } printf("%lld\n", res);}int main(){ getPrime(); int t; scanf("%d", &t); while (t--) { scanf("%lld%lld%lld", &l, &r, &k); for (ll i = l; i <= r; i++) //初始化d和ans { d[i - l] = 1; ans[i - l] = i; } solve(); } return 0;}

转载于:https://www.cnblogs.com/Archger/p/8451613.html

你可能感兴趣的文章