2017多校四 1003題 hdu 6069 Counting Divisors 分解質因數

題目連結

參考：http://blog.csdn.net/protecteyesight/article/details/76685920 ——protecteyesight

題意：

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

思路：

設n=p_1^{c_1}p_2^{c_2}...p_m^{c_m}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)d(n​k​​)=(kc​1​​+1)(kc​2​​+1)...(kc​m​​+1)

這一點是顯然的，關鍵問題就在于怎麼高效的分解質因數。

比賽時不會做然後幹脆就放棄了...後半場就去補以前的題了心态十分消極

（覺得現在的一個很大問題就是想想覺得會T就不去寫了...其實有的時候還真不一定，當然這道題蠻做的話肯定會T

但問題又不僅限于不去寫了，而是好像就直接放棄了再去思考...具體的我也說不清...sigh）

言歸正傳。

高效的做法是：并沒有對每個數去依次分解質因數，而是依次去看每個質數能成為哪些數的因數。同樣，也可以說是看 貢獻 的想法。

質數的話隻需要提前處理出 1e6 範圍内的即可，因為在 1e6 到 1e12 範圍内的數，如果沒有 1e6 範圍内的質數因子，其本身就必然是一個質數。

是以，隻需要在考慮完所有的質數因子之後再去判斷每個數最後是不是 1，如果不是，說明該數有一個大于 1e6 的質數因子，再乘上 (k + 1) 即可。

具體處理的時候：

1. 将 [l, r] 的數挪到 [0, l - r] 的區間去存，以便之後除以 prime[ ]。

2. 直接算出 [l, r] 的區間内第一個被 prime[i] 整除的數的值，而不要一個個去枚舉浪費時間。

Code:

#include <bits/stdc++.h>
#define maxn 1000000
#define mod 998244353
typedef long long LL;
bool vis[maxn + 10];
int prime[maxn + 10], tot;
LL a[maxn + 10], cnt, mul[maxn + 10];
void pre() {
    for (int i = 2; i <= maxn; ++i) {
        if (!vis[i]) {
            prime[tot++] = i;
        }
        for (int j = 0; j < tot; ++j) {
            if (i * prime[j] > maxn) break;
            vis[i * prime[j]] = true;
            if (i % prime[j] == 0) break;
        }
    }
}
void work() {
    LL l, r, k;
    scanf("%lld%lld%lld", &l, &r, &k);
    for (LL i = l; i <= r; ++i) a[i - l] = i, mul[i - l] = 1;
    LL r0 = r; r -= l;
    for (int i = 0; i < tot; ++i) {
        if (prime[i] > r0) break;
        int j = ceil((double)l / prime[i]) * prime[i] - l;

        for (int jj = j; jj <= r; jj += prime[i]) {
            LL cnt = 0;
            while (a[jj] % prime[i] == 0) ++cnt, a[jj] /= prime[i];
            mul[jj] = mul[jj] * (k * cnt % mod + 1) % mod;
        }
    }
    for (int i = 0; i <= r; ++i) if (a[i] > 1) mul[i] *= (k + 1), mul[i] %= mod;
    LL sum = 0;
    for (int i = 0; i <= r; ++i) sum += mul[i], sum %= mod;
    printf("%lld\n", sum);
}
int main() {
    pre();
    int T;
    scanf("%d", &T);
    while (T--) work();
    return 0;
}
           

d(n^kC