523
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;
}
最後更新：2017-04-03 16:59:48