蹲着还是站着？

NC23925. 蹲着还是站着？

描述

杨主席这段时间由于要找实习，所以非常焦躁。因为公司的面试都非常的难，杨主席不知道从哪入手。于是他就找了他的学长坑坑询问情况，坑坑告诉他要注重算法的学习，于是就给杨主席出了一个题目看看他算法学的怎么样，这道题是这样的：有N个人排成一排，从1到N按顺序依次编号，现在要执行N次操作，第一次操作让所有的人都蹲下，之后第二次操作让编号是2和2的倍数的人全部站起来，然后第三次操作让编号是3和3的倍数的人全部做相反的动作（站着的人蹲下，蹲下的人站起来），以此类推...，最后第N此操作让编号为N的这个人也做相反的动作。请问N次操作后，从第A个人到第B个人之间（包括A和B这两个数字,且A<B）有多少人是站着的？

输入描述

输入数据为T组数据（1<=T<=10）。
每组数据输入包含三个数字N，A，B(1<=N<=1000000，1<=A<B<=N)。

输出描述

对于每组数据，输出一个整数，表示从第A个人到第B个人之间有多少人站着。

示例1

输入:

1
5 1 3

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

C(clang 3.9) 解法, 执行用时: 3ms, 内存消耗: 232K, 提交时间: 2019-04-11 12:00:09

#include<stdio.h>
#include<math.h>

int main()
{
	int t;
	scanf("%d",&t);
	long n,a,b,a1,b1;
	while(t--)
	{
		scanf("%ld%ld%ld",&n,&a,&b);
		a1=sqrt(a);
		if(a1*a1!=a)
			a1++;
		b1=sqrt(b)+1;
		printf("%ld\n",b-a+1-b1+a1);		
	}
	return 0;
 }

C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 476K, 提交时间: 2019-04-08 10:05:57

#include<iostream>
using namespace std;
int t,n,a,b,s[1000006];
int main()
{
	cin>>t;
	while(t--)
	{
		cin>>n>>a>>b;
		int j=1;
		int cnt=b-a+1;
		while(j*j<=b)
		{
			if(j*j>=a)
			cnt--;
			j++;
		}
		cout<<cnt<<endl;
	}
	return 0;	 
}

C++11(clang++ 3.9) 解法, 执行用时: 3ms, 内存消耗: 352K, 提交时间: 2020-05-29 20:17:42

#include<bits/stdc++.h>
using namespace std;
int i,j,n,m,a,b,s;
int main(){
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d%d%d",&m,&a,&b);
		s=b-a+1;
	for(j=1;j*j<=b;j++){
		if(j*j>=a){s--;
		}
	}
	printf("%d\n",s);
	}
	
}