Pairwise Products

Misha is given a number N. You are required to help Misha determine the summation of the pairwise product of its divisors.

Example:

Input:  n = 4
Output: 14

Approach

C++

#include <bits/stdc++.h>
using namespace std;

const long long MX = 1e7;
const long long preMX = 664579;

long long spf[MX + 1], pre[preMX + 1];

long long pairwiseProduct(long long n, long long p)
{
    long long res = 1, x = n;
    for (int i = 0; i < p; ++i, x *= n)
        res += x;
    return res;
}

int main()
{

    for (int i = 2, cnt = 0; i <= MX; i++)
    {
        if (spf[i] == 0)
            spf[i] = i, pre[cnt++] = i;
        for (int j = 0; j < cnt and pre[j] <= spf[i]; ++j)
        {
            long long idx = i * pre[j];
            if (idx > MX)
                break;
            spf[idx] = pre[j];
        }
    }

    long long n = 4, res = 1, sres = 1;

    while (n != 1)
    {
        long long nn = spf[n], times = 0;
        while (n % nn == 0)
        {
            n /= nn;
            times++;
        }
        res *= pairwiseProduct(nn, times);
        sres *= pairwiseProduct(nn * nn, times);
    }
    cout << ((res * res - sres) >> 1) << "\n";

    return 0;
}