HDU_6069 Counting Divisors

題目連結

題目意思

給你三個數L,R,K讓你求滿足下面公式的答案

解題思路

由題意我們可以知道L，R最大為1e12，是以我們可以用篩法篩選sqrt(1e12)之内的所有素數。

有數論中的結論我們知道，任何一個正整數x，都可以分解成若幹個素數幂的積。

則 x = (p1^m1)* (p2^m2)* (p3^m3)* …..* (pn^mn); 其中p1,p2,p3…pn都是素數，m1,m2,m3…mn都是幂指數。

則 x 的因子個數d(x) = (m1+1)* (m2+1)*(m3+1)….(mn+1);

那麼對于x^k = ((p1^m1)* (p2^m2)* (p3^m3)* …..*(pn^mn))^k;

則 x^k = (p1^m1* k) * (p2^m2* k) * (p3^m3* k)* …..* (pn^mn*k);

則x^k的因子個數d(x^k) = (m1* k+1) * (m2* k+1) * (m3* k+1) * …..(mn k+1);

然後這道題就是讓算一個區間的K次方的因數個數之和，首先先将

1e6

之内的素數打表，然後再然後枚舉這些素數，在枚舉 [L,R] 區間中這些素數的倍數，然後根據這些倍數進行素因子分解，其實就是統計 [L,R] 區間中有多少個枚舉的素數，然後乘以 K， 在加 1 計算即可。在枚舉 [L,R] 區間值的時候，我們需要先把 [L,R] 區間中的數用數組儲存下來，然後通過數組進行素因子分解。

代碼部分

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 998244353;
const LL MAXN = 1e6+5;
int prime[MAXN], cnt;///cnt代表1e6中素數的個數
LL p[MAXN];///存放素數從0開始
///篩法求素數
void isprime()
{
    memset(prime, 0, sizeof(prime));
    cnt = 0;
    prime[1] = 1;
    for(LL i=2; i<MAXN; i++)
    {
        if(!prime[i])
        {
            p[cnt++] = i;
            for(LL j=i*i; j<MAXN; j+=i)
                prime[j] = 1;
        }
    }
}

LL f[MAXN], num[MAXN];///f[i]用來存儲L~R之間的數,在不斷的對因數相除。累積數量
int main()
{
    isprime();
    int T;
    scanf("%d", &T);
    while(T--)
    {
        LL L, R, K;
        scanf("%lld%lld%lld", &L, &R, &K);
        LL ans = 0;
        if(L == 1) 
            ans = 1, L++;
        int t = R-L;
        for(int i=0; i<=t; i++) 
            f[i] = i+L, num[i] = 1;///初始化

        for(int i=0; i<cnt&&p[i]*p[i]<=R; i++)
        {
            LL tmp = L;
            if(L % p[i]) tmp = (L/p[i]+1)*p[i];///找到第一個可以整除素數p[i]的數，不進行這步會逾時
            //cout << "tmp = " << tmp << endl;
            for(LL j=tmp; j<=R; j+=p[i])///素因子分解
            {
                LL cnt = 0;
                while(f[j-L]%p[i] == 0)
                {
                    cnt++;
                    f[j-L] /= p[i];
                }
                num[j-L] = num[j-L]*(cnt*K+1)%MOD;
            }
        }


        for(int i=0; i<=t; i++)///計算結果
        {
            //cout << "num = " << num[i] << "   f = " << f[i] << endl;
            if(f[i] == 1) 
                ans = (ans + num[i]) % MOD;
            else
                ans = (ans + num[i]*(K + 1)) % MOD;
        }
        printf("%lld\n", ans);
    }
    return 0;
}