Sums of even Divisor problem

Question

How to find sum of all even divisor of a number using formula.Or more efficiently​. Please any suggestions.

Answer 1

Here is some code, the idea is to use the multiplicative formula but pre-sieving the primes first. Perhaps the only interesting idea is that the even divisors of $x$ are exactly the divisors of $x$ that are not divisors of the odd part of $x$.

This code should work within the time limits of most contest problems:

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

const int MAX=1000010; // this will let us factorize number up to slightly less than MAX*MAX
int C[MAX];// the cribe
vector <int> P; //here we store the primes

lli sumd(lli x){
    lli res=1;
    for(int i=0;P[i]*P[i]<= x; i++){// by the prime number theorem this takes at most 2sqrt(n)/log(n) (approximately)
        lli m=1,f=1;// m is what we need to multiply the answer by at the end, f lets us build m
        while(x%P[i]==0){
            f*=P[i];
            m+=f;
            x/=P[i];
        }
        res=res*m;
    }
    if(x>1) res=res*(x+1);
    return(res);
}

int odd(int x){
    while(x%2){
        x/=2;
    }
    return(x);
}

int main(){
    for(int i=2;i<MAX;i++){// this sets up the cribe.
        if(!C[i]){
            P.push_back(i);
            for(int j=2*i;j<MAX;j+=i){
                C[j]=1;
            }
        }
    }
    int cases;
    cin >> cases;
    while(cases --){
        int x;
        cin >> x;
        cout << sumd(x)- sumd(odd (x) ) << endl;
    }
}

Answer 2

Hints:

• The sum of divisors function $\sigma$ is a multiplicative function. In other words, if $n$ and $m$ are relatively prime, then $\sigma(nm)=\sigma(n)\sigma(m)$. Moreover, if $p$ is prime, then $\sigma(p)=p+1$. Moreover $\sigma(p^k)=1+p+p^2+\cdots+p^k$, which is a geometric sum equal to $\frac{p^{k+1}-1}{p-1}$.

• The sum of the even divisors of $n$ is $\sigma(n)$ minus the sum of the odd divisors.

• If $2^k$ is the largest power of $2$ dividing $n$, then $\sigma\left(\frac{n}{2^k}\right)$ is the sum of the odd divisors of $n$.

• Putting this together, \begin{align*} \sigma(n)-\sigma\left(\frac{n}{2^k}\right)&=\sigma(2^k)\sigma\left(\frac{n}{2^k}\right)-\sigma\left(\frac{n}{2^k}\right)\\ &=\left(\sigma(2^k)-1\right)\sigma\left(\frac{n}{2^k}\right)\\ &=(2^{k+1}-2)\sigma\left(\frac{n}{2^k}\right). \end{align*}

For example, let $n=180=2^2\cdot 3^2\cdot 5$. Then, the divisors of $180$ are: $$ \{1,2,3,4,5,6,9,10,12,15,18,20,30,36,45,60,90,180\}. $$ The sum of the divisors is $$ 1+2+3+4+5+6+9+10+12+15+18+20+30+36+45+60+90+180=546. $$ The sum of the odd divisors is $$ 1+3+5+9+15+45=78. $$ The sum of the even divisors is $$ 2+4+6+10+12+18+20+30+36+60+90+180=468. $$ Observe that $468+78=546$ (as expected).

Alternately, we can use our formula to check all of this: The largest power of $2$ dividing $180$ is $2^2$, and $\frac{180}{4}=45$. Therefore, the sum we're looking for can be computed as: \begin{align*} (2^3-2)\sigma(45)&=(2^3-2)\sigma(3^2)\sigma(5)\\ &=6\cdot\frac{3^3-1}{3-1}\cdot(5+1)\\ &=6\cdot 13\cdot 6=468. \end{align*} Observe additionally that $\sigma(45)=13\cdot 6=78$, i.e., the sum of the odd divisors.