Wrong answer 18. Can anybody help me, please?

check if answer = 2 (Ferma-Euler theorem)

Do you know what's the test 62?

I noticed that all primes in factorization of N are also strong pseudoprimes to base just 2 or 3.

#include <queue>
#include <iostream>
#include <set>
#include <cstdio>
#include <algorithm>
#include <string>
#include <map>
#include <string>
#include <sstream>
using namespace std;
bool k(long double x)
{
    long double t=floor((sqrt(x)));
    if (t*t==x)
    {
        return true;
    }
    else
        return false;
}
int main()
{
    long double n;

    scanf("%lf",&n);
    long long c=n;
    if(k(n))
    {
        cout<<1;
        return 0;
    }

    for(long int i=1;i<=sqrt(n)/2+2100000;i++)
    {
        long double q=n-i*i;
        if(k(q))
        {
            printf("%d",2);
            return 0;
        }
    }
    for(long int i=sqrt(n);i>=sqrt(n)-2100000;i--)
    {
        long double q=n-i*i;
        if(k(q))
        {
            printf("%d",2);
            return 0;
        }
    }
    long long q = (long long)n;
    for ( int i = 0; i <20; i ++)
    {
        long long d = 1;
        for ( int j = 0; j < i;j++)
        {
            d*=4;
            if ( q > n)
            break;
        }
        if ( d > q)
            break;
        if( (long long)q % d==0)
        {
            long long temp = q/d - 7;
            if ( temp %8==0)
            {
                printf("%d",4);
                return 0;
            }

        }
    }

    printf("%d",3);
    return 0;
}

Do you know what's the test 29?

Edit: got the AC.

Edited by author 03.07.2012 14:20

Thanks in advance

Can anyone help me ? I have WA on test 43 .
Thanks for your attention .

I followed the algorithm of luckysundog which is posted in this forum and solved it C# and C++.
The same code in C# and C++ gives AC, but in Java it gives Time Limit Exceeded in test 45.
I improved the code to run faster but now it gives TLE 54.
I tested the code against worst case of 1000000000000037, which is a prime number. And execution time for this test was 138 milliseconds which is obviously less than 1000 (1 second).
For prime 10000000000000061, it takes 185 milliseconds.
Does anybody know what test 54 is?
Did anybody solve this problem in Java?
Can you please send me the solution to hazorman@gmail.com
Thanks,

Try  2
ans: 2
=)

Input
7

Output
4

Edited by author 12.10.2011 22:59

My algorithm is O(sqrt(n)).
I dont know why it is TLE test 13.
Any hints?

New problem 1593 was added to the Problem set. It has the same problem statements as in the problem 1073, but with bigger limitations. Thanks to Fyodor Menshikov for the idea and the implementation.