hdu 4342 History repeat itself(数学题)

题目链接：hdu 4342 History repeat itself

题意：

让你找第a个非完全平方数m，并且求前m个数的开方向下取整的和。

题解：

第一个问题：

假设第a个非平方数是X，X前面有n个平方数，则n*n<X<(n+1)*(n+1);

n*n前面的非平方数的个数是n*n-n;

首先先根据a求n,n是满足不等式  n*n-n<a的最大正整数。

不等式的解是：

(1+sqrt(1+4*a))/2;必需对这个数上取整，然后减一就是n了。

然后第a个非平方数就是  n*n+（a-n*n+n)=a+n。

第二个问题：

我们观察可以发现，第二个问题是有规律的，因为是开方向下取整，所以在两个完全平方数之前这段区间的值都是一样的，所以有公式

(2*i-1)*(i-1)，然后暴力加一下就行了，然后这只是前面n*n-1的，对于n*n到a+n的单独算一下就行，当然你也可以向kuangbin那样直接推公式。

#include<bits/stdc++.h>
#define F(i,a,b) for(int i=a;i<=b;++i)
using namespace std;

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        long long a,ans1,ans2,n;
        scanf("%lld",&a);
        n=ceil((1+sqrt(1+4*a))/2)-1;
        ans1=n+a;
        ans2=0;
        F(i,2,n)ans2+=(long long)(2*i-1)*(i-1);
        printf("%lld %lld
",ans1,ans2+(a+n-n*n+1)*n);
    }
    return 0;
}