LightOJ-1336 Sigma Function

 /*

Look at this problem, here, N <= 10^12, which means this is impossible to take all values

on an array. Therefore, it should be a line solution or simple mathematical solution.

However, you have to analyze it with pen and paper first.

I am giving a concept here:

Look, if we have N, then, we may cover all prime or composite numbers on the range of

sqrt(N). Besides, we have to find the result of even summation. So, if we have N, then,

it must have N/2 even and odd numbers. We also cover those numbers under the range of

sqrt(N/2).

*/

#include <bits/stdc++.h>

using namespace std;

#define sf scanf

#define pf printf

typedef long long LL;

const int high = 1e6+5;

void divisor_sum(int N)

{

    int i,j, x;

    for(x=1; x<=N; x++)

    {

        LL sum = 0;

        for(i=1; i*i<=x; i++)

        {

            if(x%i==0)

            {

                int div = x / i;

                if(div==i) sum+=i;

                else sum = sum+div+i;

            }

        }

        if(sum%2==1)

        {

            cout << x << ". sum = " << sum << "\n";

        }

        //cout << x << ". sum = " << sum << "\n";

    }

}

int main()

{

    //divisor_sum(25);

    int test, tc=0;

    LL N, a, b, ans;

    sf("%d", &test);

    while(test--)

    {

        sf("%lld", &N);

        a = sqrt(N);

        b = N/2;

        b = sqrt(b);

        ans = N - (a + b);

        pf("Case %d: %lld\n", ++tc, ans);

    }

    return 0;

}