Here you will find solutions of many problems on spoj. If you want solution of some problem which is not listed in blog or have doubt regarding any spoj problem (which i have solved) or any programming concept (data structure) you can mail me @ raj.nishant360@gmail.com
And my humble request to you all that don't copy the code only try to understand the logic and algorithm behind the code. I have started this because if you tried as hard as you can and still can't find any solution to the problem then you can refer to this.
You can read my answer how to start competitive programming CLICK HERE

Saturday, May 31, 2014

IITKWPCF-Help Feluda with mathematical equations

Help Feluda with mathematical equations

Given below c++ code for iitkwpcf spoj or Help Feluda with mathematical equations spoj .
Here is the explanation of logic.
Given X2  + Y2 + n = (X + Y)2
Now expanding it   
X2  + Y2 + n = X2  + Y2 + 2XY    ≡   n = 2XY   ≡  X = (n/2)*(1/y)
So we have to find only non-prime integral factor of “n/2” .and if “n” is odd then no integral “X” is possible so we will write 0 for all odd “n”.
Here my solution got accepted in 2.45 sec sad.Please help me to reduce the time complexity @ raj.nishant360@gmail.com

#include <bits/stdc++.h>
using namespace std;
#define LL long long
bool check(LL n)
{
    if(n==1)
        return true;
    for(LL i=2;i*i<=(n);i++)
        if(n%i==0)
            return true;
    return false;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        LL n,temp;
        scanf("%lld",&n);
        if(n==0)
        {
            printf("0 0\n");
            continue;
        }
        if(n&1)
        {
            printf("0\n");
            continue;
        }
        n>>=1;
        map<LL,int>mp;
        map<LL,int>::iterator t;
        for(LL i=1;i*i<=n;i++)
        {
            if(n%i==0)
            {
                if(check(i)){
                    mp[i]=1;
                }
                if(check(n/i))
                    mp[n/i]=1;
            }
        }
        printf("%d ",mp.size());
        for(t=mp.begin();t!=mp.end();t++)
            printf("%lld ",t->first);
        printf("\n");
    }
    return 0;
}