欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Counting Divisors HDU - 6069 (区间素数筛 + 一个数的所有素因子的个数 + 约数定理 + 数学)

程序员文章站 2022-06-08 12:10:35
...

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

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

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

(i=lrd(ik))mod998244353(∑i=lrd(ik))mod998244353

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

In each test case, there are 33 integers l,r,k(1lr1012,rl106,1k107)l,r,k(1≤l≤r≤1012,r−l≤106,1≤k≤107).OutputFor 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 求   l<= t<=r,  求   对多有满足条件的t 的   d(t^k)=t^k的所有 不同因子的个数    的总和

思路:想求d(t^k),先求 d(t),根据约数定理 求不同因子的个数,先把 t 表示为不同素因子的积的形式;

Counting Divisors HDU - 6069 (区间素数筛 + 一个数的所有素因子的个数 + 约数定理 + 数学)

n=p1^c1×p2^c2×p3^c3*…*pm^cm

d(n) = (C1 + 1)*(C2 + 1)*...... (Cm+1) ;表示不同因子的个数;

c1+1 为从中可以选出 1个p1,2个p1...... c1个p1,加 1就是 一个p1也不选,光p1这个素数就 c1+1 种情况,然后和其他选出的素因子结合;有一种情况就是 所有的素因子都不选,那么这种情况 就是 n个素因子为1 的这种情况;

理解了d(n),那么d(n^k)就好理解了

写代码应注意;

1,用三目运算符时,一定要加括号,就这道题而言,不加括号就是超时;

2,代码中用到了 区间素数筛, 还有最重要的时,a[] 和 sum[] 数组,sum[i] 存 sum[l+i] 的素因子个数;

a[i] = l + i; 找到 l+i的素因子时,一直除到不能整除 这个素因子位置;

3,当一个数 n,把1~根号n 中的素数 能除的都除尽了,但最终 n 不为1,那么这么剩余的n一定是个大素数;

我说这个大素数有两种情况 (1) n 本身为 素数  (2) n 把1~ 根号n中的素数除完之后,剩余的数为素数;

如 n = 14,14 把 1~根号14 中的素数都除尽后,剩下 7,7为素数;

代码:

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define ll long long  
#define Max 1000000+10
#define mod 998244353
bool is_prime[Max];  // 0~Max 之间的素数 
ll prime[Max];  // 存 0~Max 之间的素数; 
ll sum[Max];   //  sum[i]表示 l+i的因子个数; 
ll a[Max];     // a[i] = l+i; 为了素数分解; 
  
ll l,r,k;
ll num;

void Prime()
{
	num = 0;
	ll i,j;
	memset(is_prime,true,sizeof(is_prime));
    is_prime[0] = false;
    is_prime[1] = false;
    for(i = 2;i<Max;i++)     
    {
        if(is_prime[i])
        {
            prime[num++] = i;    // 找出1 ~ 1000000中的素数; 
            for(j = 2;i*j<Max;j++)
                is_prime[i*j] = false;
        }
    }
}
int main()
{
	Prime();
    ll i,j,t;
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld%lld%lld",&l,&r,&k);
        for(i = 0;i<=r-l;i++)
        {
            sum[i] = 1;    // 要进行乘法,所以要赋值为1; 
            a[i] = l+i;    //  为了把 a[i] == l+i 进行分解; 
        }
         for(i = 0;i<num;i++)
         {
             ll temp = (l/prime[i]+((l%prime[i])?1:0))*prime[i]; 
             // 三目运算符一定要加括号;,不加括号超时; 
			 //找到[l,r]中第一个能被这个素数整除的数;
             
             for(j = temp; j<=r; j += prime[i])     // 先找到能整除素数prime[i]的数; 
             {
                 ll res = 0;
                 while(a[j-l]%prime[i]==0)  // 把这个数进行素数分解; 
                 {
                     a[j-l] /= prime[i];
                     res++;
                 }
                 sum[j-l] = (sum[j-l]*((res*k+1)%mod))%mod; 
             }
         }
        ll res = 0;
        for(i = 0;i<=r-l;i++)
        {
            if(a[i]!=1) sum[i] = sum[i]*(k+1)%mod;  //分解之后,若不是1,一定是个大素数; 
            
            res = (res+sum[i])%mod; 
        }
        printf("%lld\n",res);
    }
    return 0;
}