toshiba打印机,汶上党建网,涪陵杀人案
Description
川川想给他的女朋友一些惊喜，于是他准备了好多彩灯，他的女朋友十分感动，然后让川川这样做：如果她走到了第2盏彩灯处，那么川川就要改变所有2的倍数的灯的状态(灯有两种状态，开着的和关着的)，假如一开始所有灯都是关着的，那么川川就要打开第2盏，第4盏，第6盏…，同样的道理，假如她走到的第三盏灯的位置，那么川川就要改变第3盏，第6盏，第9盏…的状态。
现在一开始所有的灯都是关着的，一共有N盏灯，川川从第2盏灯走到了第N盏灯，请问从第A盏灯跟第B盏灯之间(包含AB两盏)，有多少彩灯是开着的?
Input
三个数，N，A，B(A,B,N<10^6)
Output
第A盏灯跟第B盏灯之间(包含AB)开着的灯的数目
Sample Input
5 1 3
Sample Output
2
思路：可以看出，被按了奇数次数的灯最后是开着的，而被按了偶数次数的灯最后是关着的。而如果一个数有偶数个因子那就会被按偶数次，如果有奇数个因子就会被按奇数次。这就会涉及到质因子分解定理，即任何正数都能被分解成多个质数的幂次乘积的形式
如：
14=2*7
50=2*5^2
…
100=2^2*5^2
也就是N=(p[1]^e[1])(p[2]^e[2])……(p[k]^e[k])，其中p[i]是质数，e[i]是p[i]的幂次。而由这个公式我们又可以导出一个数有多少个因子的计算公式:FactorNumber(N)=(e[1]+1)(e[2]+1)……(e[k]+1)。
那么什么条件下满足FactorNumber(N)是奇数呢?显然必须所有的e[1],e[2],……,e[k]都必须是偶数，这样才能保证e[i]+1是奇数，结果乘积才能是奇数。而由于e[1],e[2],……,e[k]都是偶数,那么N一定是一个完全平方数(因为sqrt(N)=(p[1]^(e[1]/2))(p[2]^(e[2]/2))……*(p[k]^(e[k]/2))是整数) 。回到按灯泡的问题上来，1~100中完全平方数有1,4,9,16,25,36,49,64,81,100这10个数，也就是说最后只有编号为这10个数的灯是亮着的。
我要评论
# include <cmath>
# include <iostream>
# include <algorithm>
using namespace std;
int n, a, b, s;
int main ()
{
while (cin >> n >> a >> b)
{
if (a > b)
swap(a,b);
s = 0;
for (double i=a; i<=b; ++i)
{
double t = sqrt (i);
if (t - (int)t)
s++;
}
cout << s << endl;
}
return 0;
}
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论