2017ACM暑期多校联合训练 - Team 4 1003 HDU 6069 Counting Divisors （区间素数筛选+因子数）

题目链接

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

分析：

如果一个数n可以分解成n=p1^m1*p2m2*···*pn^mn的话（其中p1,p1···为素数），那么这个数的因子个数就为(m1+1)*(m2+1)*···*(mn+1)。

同样的，这个数由n变为n^{k的话，相应的次数前面分别乘以k即可。即n}k的因子个数为(k*m1+1)*(km2+1)*···*(kmn+1)。

这个问题解决掉之后，我们会发现数据范围太大，我们的数组分本没办法开到那么大，我们可以把数据由前半部分来推出后半部分。

先打个1e6范围内的素数表，然后枚举可行范围内的每个素数，在区间[ l , r ]内寻找所有的该素数的倍数，将其分解质因数。

到最后如果一个数没有变成1，那就说明这个数是大于1e6的质数。（质数只有1和它本身）那么如果按照规律计算的话，只需要乘上一个（k+1）就行了。

#include<iostream>

#include<stdio.h>

#include<cmath>

using namespace std;

typedef long long ll;

const int maxn=1e6+5;

const int mod=998244353;

int n;

int cnt=0;

int primes[maxn];

int vis[maxn];

void get_primes()///筛选法求出1e6之内的素数，比1e6大的素数可以通过这些素数间接的求出来

{

    int m=sqrt(maxn+0.5);///开方，循环到这个就行了

    for(int i=2; i<=m; i++)

    {

        if(!vis[i])

        {

            for(int j=i*i; j<=maxn; j+=i)

                vis[j]=1;

        }

    }

    for(int i=2; i<=maxn; i++)

        if(!vis[i])   primes[cnt++]=i;

}

ll l, r, k;

ll sum[maxn], num[maxn];

int main()

{

    get_primes();

    int T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%lld%lld%lld",&l,&r,&k);

        ll ans=0;

        ///因为l和r的范围比较大，但是它们之间的差值不会查过1e6，可以将数组缩小一点

        for(ll i=l; i<=r; i++)

        {

            sum[i-l]=1;///个数

            num[i-l]=i;///表示的是这个数

        }

        for(int i=0; i<cnt && primes[i]*primes[i]<=r; i++)///所有的素数

        {

            ///求出的是[l,r]区间中第一个能够被rimes[i]整除的数

            ll tmp=ceil((long double)l/primes[i])*primes[i];

            for(ll j=tmp; j<=r; j+=primes[i])///枚举所有的这个素数的倍数

            {

                if(num[j-l]%primes[i]==0)

                {

                    int res=0;

                    while(num[j-l]%primes[i]==0)

                    {

                        res++;

                        num[j-l]/=primes[i];

                    }

                    sum[j-l]=(sum[j-l]*(((ll)res*k+1))%mod)%mod;

                }

            }

        }

        for(ll i=l; i<=r; i++)

        {

            if(num[i-l]!=1)///那些本身是素数的数

                sum[i-l]=(sum[i-l]*(k+1))%mod;  ///大于1e6的质数

            ans=(ans+sum[i-l])%mod;

        }

        printf("%lld\n",ans);

    }

    return 0;

}

巴特西

2017ACM暑期多校联合训练 - Team 4 1003 HDU 6069 Counting Divisors （区间素数筛选+因子数）

最新文章

热门文章