hdu6069 多校Counting Divisors

　　

　　　思路：对于n^k其实就是每个因子的个数乘了一个K。然后现在就变成了求每个数的每个质因子有多少个，但是比赛的时候只想到sqrt(n)的分解方法，总复杂度爆炸，就一直没过去，然后赛后看官方题解感觉好妙啊！通过类似素数筛法的方式，把L - R的质因子给分解，就可以在O(nlogn)的时间之内把所以的数给筛出来。

/*  gyt

       Live up to every day            */

#include<cstdio>

#include<cmath>

#include<iostream>

#include<algorithm>

#include<vector>

#include<stack>

#include<cstring>

#include<queue>

#include<set>

#include<string>

#include<map>

#include <time.h>

#define PI acos(-1)

using namespace std;

typedef long long ll;

typedef double db;

const int maxn = 1e6+;

const ll maxm = 1e7;

const ll mod = ;

const int INF = 0x3f3f3f;

const ll inf = 1e15 + ;

const db eps = 1e-;

int is[maxn], pri[maxn];

ll f[maxn], num[maxn];

int cnt;

ll r, l, k;

void prim() {

    cnt=;

    memset(is, , sizeof(is));

    memset(pri, , sizeof(pri));

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

        if (!is[i]) {

            pri[++cnt]=i;

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

                is[j]=;

            }

        }

    }

}

void solve() {

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

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

        f[i-l+]=, num[i-l+]=i;

    }

    for (int i=; i<=cnt; i++) {

        ll be=l+pri[i]-l%pri[i];

        if (l%pri[i]==)  be=l;

        for (ll j=be; j<=r; j+=pri[i]) {

            ll sum=;

            while (num[j-l+]%pri[i]==) {

                sum++;

                num[j-l+]/=pri[i];

            }

            f[j-l+]=f[j-l+]*(k*sum%mod+)%mod;

        }

    }

    ll ans=;

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

        if (num[i-l+]!=)  f[i-l+]=f[i-l+]*(k+)%mod;

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

    }

    cout<<ans<<endl;

}

int main() {

    int t = ;

    //freopen("in.txt", "r", stdin);

    scanf("%d", &t);

    prim();

    while(t--)

        solve();

    return ;

}

　　解释：

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

        f[i-l+]=, num[i-l+]=i;

}

　　如果不进行这一步，那么数是1~1^12存不下，但是我们已知r-l<=1e6，这样就可以存下了。

　　f[i]表示当前的因数个数，num[i]，从l到r(下标1-(r-l+1))的数。

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

        if (num[i-l+]!=)  f[i-l+]=f[i-l+]*(k+)%mod;

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

}

　　判断当前这个数还有没有素数因子。