21 Days Training // Day 6

T1. Divisor Count

Notice that :

1. The function d(n) is multiplicative.
2. For d(p^q) , it equals to q+1 . Here, p is a prime, q is a non-negative number.

So for d(\Pi_{i=1}^k p_i^{q_i}) , we can first decompose its prime factors, and use propery 2 to get d(p_i^{q_i}), and then use property 1 to multiply them together.
Since N \le 1 \times 10^6 , this algorithm may pass this problem.

Code :

#include <bits/stdc++.h>
using namespace std;
const long long LIM=1000000;
bitset<LIM+10> isprime, vis;
long long lprime[LIM+11];

void preprocess() {
    lprime[1]=0;
    isprime[2]=1, vis[2]=1;
    lprime[2]=2;
    for (long long j=4;j<=LIM+10;j+=2) vis[j]=1, lprime[j]=2;
    for (long long i=3;i<=LIM+10;i++) {
        if (vis[i]) continue;
        lprime[i]=i, isprime[i]=1, vis[i]=1;
        for (long long j=2*i;j<=LIM+10;j+=i) vis[j]=1, lprime[j]=(lprime[j]?lprime[j]:i);
    }
}

int main() {
    preprocess();
    long long N;cin >> N;
    long long gsum=0;
    for (long long i=1;i<=N;i++) {
        if (i==1) gsum+=1;
        else if (isprime[i]) gsum+=2;
        else {
            map<long long, long long> pfac;
            long long bk=i;
            while (lprime[bk]) {
                if (pfac.find(lprime[bk])==pfac.end()) pfac[lprime[bk]]=0;
                pfac[lprime[bk]]++;
                bk/=lprime[bk];
            }
            long long f=1;
            for (map<long long, long long>::iterator it=pfac.begin();it!=pfac.end();it++) {
                f*=it->second+1;
            }
            gsum+=f;
        }
    }
    cout << gsum;
    return 0;
}