李华

用户名：2645479600

访问量：18663

签　名：

等　　级
排　　名	478
经　　验	4691
参赛次数	2
文章发表	22
年　　龄	22
在职情况	学生
学　　校	华软、江理
专　　业	电信、计算机

　　自我简介：

欢迎探讨

TA的其他文章

蓝桥杯算法提高VIP-3000米排名预测-题解(C++代码)---求出全部排列，逐个判断
浏览：624

蓝桥杯历届试题-最大子阵-题解(C语言代码)---dp最大子段和思想（详细）
浏览：2096

蓝桥杯2015年第六届真题-切开字符串（C++代码）---substr的简单枚举和map去重
浏览：725

你可能喜欢

C语言程序设计教程（第三版）课后习题10.1 （C++代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

蓝桥杯2014年第五届真题-生物芯片-题解(C语言代码)---怀疑隔壁C++写的有遗漏的错误点，解释详细

　　作者: 李华　　　　发表时间：2020-03-05 20:02:18 浏览：512　|　评论：0　

原题链接：蓝桥杯2014年第五届真题-生物芯片

怀疑隔壁答案错误的地方：
隔壁两个C++答案输入（20,9,16）结果是7，我的代码结果是6。正确的结果应该是灭掉首尾2盏，保留中间6盏，答案是6。应当注意完全平方数个数的处理
解题思路：
1.看数据范围最大可达10^15次方，暴力跑数组一定会超时，故肯定存在巧计

----
2.观察一下可以发现，每个灯，如果变换偶数次就是灭的，变换奇数次就是亮的。那么我们求结果可以直接拿R-L+1（R~L的灯个数）减去变换偶数次的灯，那么剩下的就是亮的灯。

---
3.那么我们怎么求出变换次数是偶数次的灯呢？其实，所谓变换次数，就是这个灯的因数个数减一，因数个数减一是多少就变换多少次。
（为什么要减1请看下一条）

---
4.那么我们怎么知道因数的个数是奇数还是偶数？规律是这样的：完全平方数的因数个数是奇数，非完全平方数的个数是偶数。什么意思呢？就是4能被1,2,4整除，因数个数是3；9能被1,3,9整除，因数个数也是3，自己列举一下就可以发现完全平方数的因数个数全都是奇数。但是题目中，不会对1整除，所以完全平方数因数个数是奇数就意味着变换偶数次，完全平方数因数个数是偶数就意味着变换奇数次。
**原理:随便举个数字16为例，一般的数字都是两两凑成一对的积等于结果，你看，比如1x16=16,2x8=16。但是偏偏他多了一个4x4=16。它自己就可以凑成一对。所以它因数个数是5个，是个奇数。所有的完全平方数都一样，因数是奇数**

---
5.现在我们知道，在L~R之间，只有某个灯的变换次数是偶数的会熄灭，即是完全平方数的灯会熄灭。我们只需要统计L~R之间有多少个完全平方数，最后减掉它就行了。
L~R之间完全平方数个数求法：对L和R分别开方。根号L和根号R之间，有多少个整数，L和R之间就有多少个完全平方数。
##### 原理：例如求100~200之间的完全平方数个数，根号100等于10，根号200等于14.14。10~14.14之间的整数，它们各自的平方都不会超过100~200的范围，个数是5个。

---
6.最后的结果就是R~L灯泡的个数减去，根号L和根号R之间的整数result。
式子:（R-L+1）- result。下面请看代码
```cpp
#include <stdio.h>
#include <math.h>
long long N,L,R;
int get_num(double first,double second)
{
	int count_=0;
	for(int i=first;i<=second;i++)
	{
		count_++;
	}
	if(first-(int)first>0) count_--;
	return count_;
} 
int main()
{
	scanf("%ld %ld %ld",&N,&L,&R);	//数据读入
	double first= sqrt(L);
	double second=sqrt(R);	//最大15次方，开过根号不会爆范围的
	int result=get_num(first,second);	//判断first到second两个小数之间有多少个整数 
	printf("%d",R-L+1-result);
	return 0;
}
```

0.0分

9 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

李华

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C++代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

用筛法求之N内的素数。（C++代码）

蓝桥杯2014年第五届真题-生物芯片-题解(C语言代码)---怀疑隔壁C++写的有遗漏的错误点，解释详细

评论区

精彩推荐

C二级辅导-进制转换（C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

回文串（C语言代码）

C语言考试练习题_排列（C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

GC的苦恼（C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

李华

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C++代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

用筛法求之N内的素数。 （C++代码）

蓝桥杯2014年第五届真题-生物芯片-题解(C语言代码)---怀疑隔壁C++写的有遗漏的错误点，解释详细

评论区

精彩推荐

C二级辅导-进制转换 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

回文串 （C语言代码）

C语言考试练习题_排列 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言考试练习题_一元二次方程 （C语言代码）

GC的苦恼 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

用筛法求之N内的素数。（C++代码）

　　评论区

C二级辅导-进制转换（C语言代码）

回文串（C语言代码）

C语言考试练习题_排列（C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

GC的苦恼（C语言代码）