当前位置:首页 > 开发 > 移动开发 > 正文

HDU 4342 History repeat itself 模拟

发表于: 2012-08-07   作者:aijuans   来源:转载   浏览:
摘要: 来源:http://acm.hdu.edu.cn/showproblem.php?pid=4342 题意:首先让求第几个非平方数,然后求从1到该数之间的每个sqrt(i)的下取整的和。 思路:一个简单的模拟题目,但是由于数据范围大,需要用__int64。我们可以首先把平方数筛选出来,假如让求第n个非平方数的话,看n前面有多少个平方数,假设有x个,则第n个非平方数就是n+x。注意两种特殊情况,即

来源:http://acm.hdu.edu.cn/showproblem.php?pid=4342

题意:首先让求第几个非平方数,然后求从1到该数之间的每个sqrt(i)的下取整的和。

思路:一个简单的模拟题目,但是由于数据范围大,需要用__int64。我们可以首先把平方数筛选出来,假如让求第n个非平方数的话,看n前面有多少个平方数,假设有x个,则第n个非平方数就是n+x。注意两种特殊情况,即n + x是完全平方数,则加1即可。另一种是n是完全平方数。之后求和的时候,注意到一个平方数到另一个平方数之间的数开根号下取整的结果是一样的。因此不需要一个一个循环。

代码:

#include <iostream>#include <cstdio>#include <string.h>#include <cmath>using namespace std;typedef long long LL;#define CLR(arr,val) memset(arr,val,sizeof(arr))LL N = 3000000000;const int M = 1000010;LL squre[M];void init(){	CLR(squre,0);	int cnt = 0;	for(long long i = 1;;++i){	  if(i * i > N)		  break;	  //printf("ss");	  squre[cnt++] = i * i;	}	//for(int i = 0;i < 10; ++i)	//	printf("%d ",squre[i]);	//printf("\n");}int find(int x){	int ans = 0;	for(int i = 0;;++i){		if(squre[i] <= x && squre[i+1] > x){		  ans = i;		  break;		}	}	return ans + 1;}int min(int a,int b){	return a<b?a:b;}int main(){	init();	int numcase;	scanf("%d",&numcase);	while(numcase--){	   __int64 n;	   scanf("%I64d",&n);	   int x = find(n);	   n = n + x;	   __int64 y = sqrt(n*1.0);	   __int64 z = n / y;	   if(y == z)		   n++;	   __int64 sum = 1;	   __int64 p = 2,q = 1;	   while(p <= n){		     __int64 s = sqrt(squre[q] + 0.5) - 1;			 __int64 mmin = min(n,squre[q] - 1);			 __int64 num = mmin - p + 1 ;			 sum += (s * num);			 p = mmin + 1;			 q++;	   }	   printf("%I64d %I64d\n",n,sum);	}	return 0;}


HDU 4342 History repeat itself 模拟

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
Linux is for people who want to know why it works. Mac is for people who don't want to know w
Problem Description A robot has been programmed to follow the instructions in its path. Instr
Robot Motion Problem Description A robot has been programmed to follow the instructions in it
Running Rabbits Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Othe
Robot Motion Problem Description A robot has been programmed to follow the instructions in it
题目:http://acm.hdu.edu.cn/showproblem.php?pid=4414 CSUST:点击打开链接 Finding crosses Time
效果图(转自:http://www.ok22.org/art_detail.aspx?id=93) 前台的(repeat.asp)代码 C#代码 <%@ P
HDU 3912 Turn Right 【水题 模拟搜索】 Turn Right Time Limit: 6000/2000 MS (Java/Others) Memor
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1002 题目要求:输入t 为测试组数,然后输入
The Donkey of Gui Zhou Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Ja
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号