HDU 4342 水数学

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

HDU 4342 水数学

prime7 2013-07-01 13:33:00 浏览293 评论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;
}


用云栖社区APP,舒服~

【云栖快讯】诚邀你用自己的技术能力来用心回答每一个问题,通过回答传承技术知识、经验、心得,问答专家期待你加入!  详情请点击

网友评论

prime7
文章209篇 | 关注0
关注
为您提供简单高效、处理能力可弹性伸缩的计算服务,帮助您快速构建更稳定、安全的应用,提升运维效... 查看详情
RDS是一种稳定可靠、可弹性伸缩的在线数据库服务。支持MySQL、SQL Server、Po... 查看详情
阿里云总监课正式启航

阿里云总监课正式启航