HDU 4342 水数学

题意：给出一个n，需要求出第n个非完全平方数m，和前m个数的开方取下整数。

这题首先能发现 i^2 之前有 i^2-i个非完全平方数，所以只要找出相邻的一个区间里存在n就可以确定第n个数的值m。再根据m取下整找出和就可以，貌似%lld是超时的，所以我很贱的打了个表。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long ans[75000];
int main()
{
    int t;
    long long n;
    for(long long i=1; i<=73000; i++)
        ans[i]=i*(i-1);
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld",&n);
        long long i=1,ans1,ans2=0;
        while(i)
        {
            if(ans[i]<n&&n<=ans[i+1])
            {
                ans1=i*i+n-i*(i-1);
                break;
            }
            i++;
        }
        long long j=1;
        while(j*j<ans1)
            ans2+=(2*j-1)*(j-1),j++;
        ans2+=(j-1)*(ans1-(j-1)*(j-1)+1);
        printf("%lld %lld\n",ans1,ans2);

    }
    return 0;
}