HDU 4342 水数学

  1. 云栖社区>
  2. 博客列表>
  3. 正文

HDU 4342 水数学

prime7 2013-07-01 13:33:00 浏览363 评论0

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

题意:给出一个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;
}


【云栖快讯】阿里云栖开发者沙龙(Java技术专场)火热来袭!快来报名参与吧!  详情请点击

网友评论