What is test 3?

I tried

1 (output 2)
2 (output 3)
3 (output 2)

All of those are correct...

maybe the problem can be abstracted as the following one:

n,m are integers, n given, find the smallest m such that [n/m]==[n/(m+1)] holds, where [] denotes the floor() function.

well, anyone has any ideas?

I got TLE on testcase 3 and I know test3 is testing near 10^18. Im using the square root method to solve the problem and the loop starts with the value from the square root function. However for numbers that are close to 10^18, the loop will run approximately 30,000 times and I know this is the problem with my solution. Can anyone tell me some ways that I could use to make the solution faster?

btw I'm doing this in C++.

Thanks :)

If you want to do it "as is" you got TLE. If you are in intellectual minority you got wa2. =) But how to solve it at 1 second? 10^18 input. approx. o(n) algo needed.
please tell me an idea! Thx a lot.

my code:

// 1705.cpp : Defines the entry point for the console application.
//

#include <iostream>
using namespace std;
double sqroot(double);
int main()
{
    int t;
    cin>>t;
    long long int input[50001];
    long long int output[50001];
    for(int i=0;i<t;i++)
    {
        scanf("%lli",&input[i]);
        long long int k=2;
        k=sqroot((double)input[i]);
        if(k<1) k = 1;
        while(true )
        {
            if(input[i]/k==(input[i]/(k+1)))
                break;
            else
                k++;
        }
        output[i]=k;
    }
    for(int i=0;i<t;i++)
        printf("%lli\n",output[i]);
    return 0;
}

inline double sqroot(double n)
{
    double begin=0;
    double end=n;
    double res=0;
    double precision=0.1;
    while(end-begin>precision)
    {
        res=(begin+end)/2;
        if(res*res>n)
            end=res;
        else
            begin=res;
    }
    return res;
}
for n=10^18 loop execute about 30000 times
May this be the couse of time limit??

please, any hint

Just as title. Would somebody explain it to me without spoiling the problem?

Rejudging of the contest after the contest is a VERY BAD THING! I am SURE that a lot of people who found solution for problem F can find error and write own sqrt function for int64.
BUT if you have not tests that fails this on the contest you CAN NOT do rejudge after IT. YOU CAN CHANGE THE DESCRIPTION OF THE PROBLEM TO SATISFY THE DATA SET BUT YOU CAN NOT CHANGE DATA SET!
In this case results of the contest is not objective at all.

Edited by author 05.04.2009 01:58

Why on the 1 test the corect answer is not 2 2 3