LightOj - 1336 - Sigma Function

Problem Link :  http://lightoj.com/volume_showproblem.php?problem=1336

Idea : Think about the problem naively, we need to iterate all  the number between 1 to n and find out if its SOD(sum of divisors) is odd or even.If a number is n then it can be written as,

  n=p1^e1*p2^e2*p3^e3.

and SOD  value can be written as ,

      SOD(n)=(p1^(e1+1)-1)/p1-1 *(p2^(e2+1)-1)/p2-1 * (p3^(e3+1)-1)/p3-1

from this equation we can said that if SOD value is odd then the power  of each prime factor should be EVEN except 2.Because ,only even power of a prime factor, gives odd value.For example ,

sigma(3^4)=3^4+3^3+3^2+3^1+3^0=121 which is odd.

and

sigma(3^3) = 3^3+3^2+3^1+3^0= 40 which is even.

Lets,talk about the prime number 2.For ,even or odd each time sigma value for prime factor 2 is odd.

A number n can be written as,

 n=2^2i*p^2  , for odd value .2^2i gives odd value and p^2 for other prime numbers also gives odd value.odd*odd value is a odd value.

So,( 2^i*p)^2=n

     2^i*p = sqrt(n).

and other odd value is,

n=2^(2i+1)*p^2

 ( 2^i*p)^2=n/2

2^i*p = sqrt(n/2)

So,Even value will be, n-sqt(n)-sqrt(n/2).

Code First Then see solution

  Code :

  #include <bits/stdc++.h>

using namespace std;

int main()
{
    int t,l=0;
    cin>>t;
    while(t--)
    {
        l++;
        long long n;
        cin>>n;
        long long ans=0;
        ans=sqrt(n);
        ans+=sqrt(n/2);
        cout<<"Case "<<l<<": "<<n-ans<<endl;
    }
    return 0;
}