この問題は、\(O(N)\) 時間で解くこともできます。

線形篩を用いることで、\(i=1,2,\ldots,N\) について、\(i\) の約数の個数 \(d(i)\) を求めることができます。

\(\operatorname{lpf} _ i\coloneqq i\) の最小素因数 とします。 線形篩は、\(\dfrac n{\operatorname{lpf} _ n}\rightarrow n\) なる遷移のみを考えることで \(i=2,3,\ldots,X\) についての \(\operatorname{lpf} _ i\) を時間計算量 \(\Theta(X)\) で全て求めるアルゴリズムです。 線形篩の詳細はこちらの解説にあるリンクを参考にしてください。

\(\operatorname{lpf} _ n\) が求まっているとき、\(m=\dfrac n{{\operatorname{lpf} _ i} ^ k}\ (k\) は整数 \(,m\not\equiv0\pmod{\operatorname{lpf} _ i})\) によって \(d(n)\) を次のように再帰的に求めることができます。

\[d(n)=\left\{\begin{matrix}1&\ &(n=1)\\ d(m)(k+1)&&(n\neq1)\end{matrix}\right.\]

\(m\) は愚直に求めても全体で \(O(N)\) 時間になることが示せますし、線形篩で \(\operatorname{lpf} _ i\) を求めるのと並行して求めてもよいです。

あとは、\(i=1,2,\ldots,N-1\) について、\(d(i)d(N-i)\) を求めて合計すればよいです。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <numeric>

int main(){
    using namespace std;

    unsigned N;
    cin >> N;
    vector<unsigned> divisor_count(N + 1);

    // 線形篩で d(i) を求める
    {
        vector<unsigned> primes, least_prime_factor(N + 1), prev_divisor(N + 1, 1), prime_power(N + 1, 1);
        for(unsigned i = 2; i <= N; ++i){
            if(!least_prime_factor[i]){
                primes.emplace_back(i);
                least_prime_factor[i] = i;
                prime_power[i] = 1;
            }
            for(const auto p : primes){
                if(p * i > N)break;
                least_prime_factor[p * i] = p;
                if(p == least_prime_factor[i]){
                    prev_divisor[p * i] = prev_divisor[i];
                    prime_power[p * i] = prime_power[i] + 1;
                    break;
                }
                prev_divisor[p * i] = i;
                prime_power[p * i] = 1;
            }
        }
        divisor_count[1] = 1;
        for(unsigned i = 2; i <= N; ++i)divisor_count[i] = divisor_count[prev_divisor[i]] * (prime_power[i] + 1);
    }
    
    // ∑_i d(i)d(N - i) が答え
    cout << inner_product(begin(divisor_count), end(divisor_count), rbegin(divisor_count), 0UL) << endl;
    
    return 0;
}